1 条题解

  • 0
    @ 2025-10-8 17:03:08
    #include <bits/stdc++.h>//优化了当前弧)
    using namespace std;
    typedef long long LL;
    const int N=510,M=250000;
    struct node{int x,y;LL f; int pre;}a[M];int alen,last[N],cur[N];
    void ins(int x,int y,LL f)
    {
        alen++;a[alen]=node{x,y,f,last[x]};last[x]=alen;
        alen++;a[alen]=node{y,x,0,last[y]};last[y]=alen;
    }
    
    int h[N],st,ed,n,m;
    bool bfs()
    {
        deque<int>q;q.clear();
        memset(h,0,sizeof(h));h[st]=1;
        q.push_back(st);
        while(!q.empty())
        {
            int x=q.front();q.pop_front();
            for(int k=last[x];k>0;k=a[k].pre)if(a[k].f)
            {
                int y=a[k].y;
                if(h[y]==0)
                {
                    h[y]=h[x]+1;
                    q.push_back(y);
                }
            }
        }
        return h[ed]>0;
    }
    
    LL dinic(int x,LL f)
    {
        if(x==ed)return f;
        LL sx=0;
        for(int k=cur[x];k;k=a[k].pre)if(a[k].f)
        {
            int y=a[k].y;
            cur[x]=k;//k之前的边对于x已经没有意义 
            if(h[y]==h[x]+1)
            {
                LL sy=dinic(y,min(a[k].f,f-sx));
                a[k].f-=sy;a[k^1].f+=sy;
                sx+=sy;if(sx==f)return f;
            }
        }
        if(sx==0)h[x]=0;
        return sx;
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&m,&st,&ed);ed+=n;
        alen=1;memset(last,0,sizeof(last));
        for(int i=1,x;i<=n;i++)
        {
            scanf("%d",&x);
            ins(i,n+i,x);
    
        }
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            ins(n+x,y,1LL<<60);
            ins(n+y,x,1LL<<60);
        }
        LL s=0;
        while( bfs() )
        {
            memcpy(cur,last,sizeof(int)*(2*n+2)); 
            s+=dinic(st,(LL)1<<62);
        }
        printf("%lld",s);
        return 0;
    }
    
    • 1

    信息

    ID
    2816
    时间
    1000ms
    内存
    32MiB
    难度
    9
    标签
    递交数
    13
    已通过
    5
    上传者