1 条题解

  • 1
    @ 2023-6-10 9:33:21
    #include<bits/stdc++.h>
    using namespace std ;
    const int maxn=110;
    const int oo=1000000000;
    
    typedef struct EDGE{
        int u,v;
        int c,f,next;
        EDGE (){
            u=v=c=f=0;
            next=-1;
        }
        EDGE (int a,int b,int d,int e,int g){
            u=a;v=b;c=d;f=e;next=g;
        }
    }E;
    E edge[100*maxn+10];
    int len=-1,head[maxn],n,m;
    int vis[maxn],dis[maxn];
    int cur[maxn];
    int allp;//总的点个数
    int S,T;//源点和汇点的编号
    void E_add (int s,int t,int x,int y){
        edge[++len]=EDGE (s,t,x,y,head[s]);
        head[s]=len;
    }
    void init (){
        cin >>m >>n;
        int i,j;
        S=n+1;
        T=n+2;
        allp=T;
        memset (head,-1,sizeof (head));
        while (1){
            scanf ("%d%d",&i,&j);
            if (i==-1&&j==-1) break;
            E_add (i,j,1,0);
            E_add (j,i,0,0);
        }
        for (i=m+1;i<=n;i++) {
            E_add (i,T,1,0);
            E_add (T,i,0,0);
        }
        for (i=1;i<=m;i++) { 
            E_add (S,i,1,0);
            E_add (i,S,0,0);
        }
    }
    int bfs (){
        memset (vis,0,sizeof(vis));
        int q[100*maxn],headx=0,tail=0;
        int now,i;
        q[tail++]=S;
        vis[S]=1;
        dis[S]=1;
        while (headx<tail){
            now=q[headx++];
            for (i=head[now];i!=-1;i=edge[i].next){
                if (!vis[edge[i].v]&&edge[i].c>edge[i].f) {
                    q[tail++]=edge[i].v;
                    dis[edge[i].v]=dis[now]+1;
                    vis[edge[i].v]=1;
                }
            }
        }
        return vis[T];
    }
    int dfs (int x,int fmax){
        if (x==T||fmax==0) return fmax;
        int f,flow=0,&now=cur[x];
        for (;now!=-1;now=edge[now].next){
            if (dis[edge[now].v]==dis[x]+1&&(f=(dfs (edge[now].v,min(fmax,edge[now].c-edge[now].f))))){
                flow+=f;
                edge[now].f+=f;
                edge[now^1].f-=f;
                fmax-=f;
                if (fmax==0) break;
            }
        }
        return flow;
    }
    int dinic (){
        int flow=0,i;
        while (bfs ()){
            for (i=1;i<=allp;i++) cur[i]=head[i];
            flow+=dfs (S,oo);
        }
        return flow;
    }
    int main (){
        init ();
        printf ("%d\n",dinic ());
        return 0;
    }
    
    
    • 1

    信息

    ID
    323
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    24
    已通过
    11
    上传者