HDU 3549 Flow Problem（最大流+EK邻接表||邻接矩阵||dinic算法模板比较）

柔光的暖阳◎ 2022-06-09 11:16 236阅读 0赞

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

Input

The first line of input contains an integer T, denoting the number of test cases.  
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)  
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

Output

For each test cases, you should output the maximum flow from source 1 to sink N.

Sample Input

2
    3 2
    1 2 1
    2 3 1
    3 3
    1 2 1
    2 3 1
    1 3 1

Sample Output

Case 1: 1
    Case 2: 2

题解：

这是一道标准的网络流炒鸡入门题目，正好最近学了3种网络流模板，第一种是紫书上的EK邻接表写法，用时202ms。。可能与stl较慢和这题为稠密图有关，第二种是我之前保存的EK邻接矩阵的写法，用时124ms，第三种是dinic算法，也是用时124ms。。。看来数据较小比较不出来差距

主要是测试一下模板的优劣性

第一种代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-5
    #define maxn 20
    struct edge//存边
    {
        int from,to,cap,flow;//cap为容量，flow为流量
        edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
    };
    vector<edge>ed;
    vector<int>G[maxn];//存第i个点连接的第j条边的标号
    int a[maxn];//存起点到i的可改进量。。不太懂，照着紫书打的
    int p[maxn];//最短路树上p的入弧编号
    int m,n;
    void init()
    {
        for(int i=1;i<=n;i++)
            G[i].clear();
        ed.clear();
    }
    void addEdge(int from,int to,int cap)
    {
        ed.push_back(edge(from,to,cap,0));
        ed.push_back(edge(to,from,0,0));//反向加边
        m=ed.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    int Maxflow(int s,int t)//s为源点，t为汇点
    {
        int flow=0;
        while(1)
        {
            memset(a,0,sizeof(a));
            queue<int>q;
            q.push(s);
            a[s]=INF;
            while(!q.empty())
            {
                int x=q.front();
                q.pop();
                for(int i=0;i<G[x].size();i++)
                {
                    edge &e=ed[G[x][i]];
                    if(!a[e.to]&&e.cap>e.flow)
                    {
                        p[e.to]=G[x][i];
                        a[e.to]=min(a[x],e.cap-e.flow);
                        q.push(e.to);
                    }
                }
                if(a[t])
                    break;
            }
            if(!a[t])
                break;
            for(int e=t;e!=s;e=ed[p[e]].from)
            {
                ed[p[e]].flow+=a[t];
                ed[p[e]^1].flow-=a[t];
            }
            flow+=a[t];
        }
        return flow;
    }
    int main()
    {
        int i,j,test,q,x,y,z,s,t,num;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%d%d",&n,&num);
            init();
            s=1;
            t=n;
            while(num--)
            {
                scanf("%d%d%d",&x,&y,&z);
                addEdge(x,y,z);
            }
            printf("Case %d: %d\n",q,Maxflow(s,t));
        }
        return 0;
    }

第二种：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-5
    #define maxn 20
    int r[maxn][maxn]; //残留网络，初始化为原图
    bool visit[maxn];
    int pre[maxn];
    int m,n;
    bool bfs(int s,int t)  //寻找一条从s到t的增广路，若找到返回true
     {
         int p;
         queue<int>q;
         memset(pre,-1,sizeof(pre));
         memset(visit,false,sizeof(visit));
    
        pre[s]=s;
         visit[s]=true;
         q.push(s);
         while(!q.empty())
         {
             p=q.front();
             q.pop();
             for(int i=0;i<=n;i++)
             {
                 if(r[p][i]>0&&!visit[i])
                 {
                     pre[i]=p;
                     visit[i]=true;
                     if(i==t) return true;
                     q.push(i);
                 }
             }
         }
         return false;
     }
    
    int EdmondsKarp(int s,int t)
     {
        int flow=0,d,i;
        while(bfs(s,t))
        {
            d=INF;
            for(i=t;i!=s;i=pre[i])
                d=d<r[pre[i]][i]? d:r[pre[i]][i];
            for(i=t;i!=s;i=pre[i])
            {
                r[pre[i]][i]-=d;
                r[i][pre[i]]+=d;
            }
            flow+=d;
        }
        return flow;
     }
    int main()
    {
        int i,j,test,q,x,y,z,s,t;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%d%d",&n,&m);
            memset(r,0,sizeof(r));
            s=1;
            t=n;
            while(m--)
            {
                scanf("%d%d%d",&x,&y,&z);
                r[x][y]+=z;
            }
            printf("Case %d: %d\n",q,EdmondsKarp(s,t));
        }
        return 0;
    }

第三种：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-5
    #define maxn 20
    struct node
    {
        int c,f;
    }p[maxn][maxn];
    int s,t;
    int pre[maxn];
    int n,m;
    int bfs()
    {
        memset(pre,0,sizeof(pre));
        queue<int>q;
        q.push(s);
        pre[s]=1;
        while(!q.empty())
        {
            int d=q.front();
            q.pop();
            for(int i=1;i<=n;i++)
            {
                if(!pre[i]&&p[d][i].c-p[d][i].f)
                {
                    pre[i]=pre[d]+1;
                    q.push(i);
                }
            }
        }
        return pre[t]!=0;
    }
    int dinic(int pos,int flow)
    {
        int f=flow;
        if(pos==t)
            return flow;
        for(int i=1;i<=n;i++)
        {
            if(p[pos][i].c-p[pos][i].f&&pre[pos]+1==pre[i])
            {
                int a=p[pos][i].c-p[pos][i].f;
                int temp=dinic(i,min(a,flow));
                p[pos][i].f+=temp;
                p[i][pos].f-=temp;
                flow-=temp;
            }
        }
        return f-flow;
    }
    int slove()
    {
        int sum=0;
        while(bfs())
        {
            sum+=dinic(s,INF);
        }
        return sum;
    }
    int main()
    {
        int i,j,test,q,x,y,z;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%d%d",&n,&m);
            memset(p,0,sizeof(p));
            s=1;
            t=n;
            while(m--)
            {
                scanf("%d%d%d",&x,&y,&z);
                p[x][y].c+=z;
            }
            printf("Case %d: %d\n",q,slove());
        }
        return 0;
    }