最大流

小咪咪 2022-08-04 10:41 146阅读 0赞

\[HDU 1532\] ([http://acm.hdu.edu.cn/showproblem.php?pid=1532][http_acm.hdu.edu.cn_showproblem.php_pid_1532])

题目描述：  
Drainage Ditches（排水沟）

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 12521 Accepted Submission(s): 5971

Problem Description  
Every time it rains on Farmer John’s fields, a pond（池塘） forms over Bessie’s favorite clover（三叶草） patch（小块土地）. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed（安装） regulators（调节阀） at the beginning of each ditch, so he can control at what rate water flows into that ditch.  
Farmer John knows not only how many gallons（加仑） of water each ditch can transport per minute but also the exact layout（布局） of the ditches, which feed out of the pond and into each other and stream in a potentially（可能的） complex network.  
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input  
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections（十字路口） points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output  
For each case, output a single integer, the maximum rate at which water may emptied（倒空） from the pond.

Sample Input  
5 4  
1 2 40  
1 4 20  
2 4 20  
2 3 30  
3 4 10

Sample Output  
50

Source  
USACO 93

言简意赅：  
题目给出起点1和终点M，还有各个边的最大流量，求由始点到终点的最大流量。  
此题为最大流模板题，直接套用即可。  
代码实现：

#include <iostream>
    #include <stdio.h>
    
    using namespace std;
    const int oo=1e9;//oo表示无穷大
    const int mm=111111;//mm表示边的最大数量，但要是原图的两倍，在加边的时候都是双向的
    const int mn=999;//mn表示点的最大数量
    int node,src,dest,edge;//node表示节点数，src表示源点，dest表示汇点，edge用来统计边数
    int ver[mm],flow[mm],next1[mm];//ver[]表示边指向的节点，flow[]表示边的容量，next[]表示链表的下一条边
    int head[mn],work[mn],dis[mn],q[mn];//head表示链表头，work为临时链表头，dis表示距离
    
    int min(int a,int b)
    {
        return a<b?a:b;
    }
    
    void prepare(int _node,int _src,int _dest)//初始化链表和图的信息
    {
        node = _node;
        src = _src;
        dest =_dest;
        for(int i=0; i<node; i++)
        {
            head[i]=-1;
        }
        edge=0;
    }
    
    void addedge(int u,int v,int c)//加一条由u到v流量为c的边
    {
        ver[edge]=v;
        flow[edge]=c;
        next1[edge]=head[u];
        head[u]=edge++;
        ver[edge]=u;
        flow[edge]=0;
        next1[edge]=head[v];
        head[v]=edge++;
    }
    
    bool Dinic_bfs()//广搜计算出每个点与源点的最短距离，若不能达到汇点，则说明算法结束
    {
        int i,u,v,l,r;
        r=0;
        for(i=0; i<node; i++)
        {
            dis[i]=-1;
        }
        dis[q[r++]=src]=0;
        for(l=0; l<r; l++)
        {
            for(i=head[u=q[l]]; i>=0; i=next1[i])
            {
                if(flow[i]&&dis[v=ver[i]]<0)
                {
                    //这条边必须由剩余流量
                    dis[q[r++]=v]=dis[u]+1;
                    if(v==dest) return 1;
                }
            }
        }
        return 0;
    }
    
    int Dinic_dfs(int u,int exp)//寻找可行流的增广路算法，按节点的距离来找，加快算法
    {
        if(u==dest) return exp;
        for(int &i=work[u],v,tmp; i>=0; i=next1[i]) /**work 是临时链表头，这里用i 引用它，这样寻找过的边不再寻找*/
        {
            if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
            {
                flow[i]-=tmp;
                flow[i^1]+=tmp;//正反向边容量改变
                return tmp;
            }
        }
        return 0;
    }
    
    int Dinic_flow()//求最大流，知道没有可行流
    {
        int i,ret=0,delta;
        while(Dinic_bfs())
        {
            for(i=0; i<node; i++)
                work[i]=head[i];
            while(delta=Dinic_dfs(src,oo))
                ret+=delta;
        }
        return ret;
    }
    
    int main()
    {
        int n,m,a,b,c;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            prepare(m+1,1,m);//总共m+1个节点，始点，终点
            while(n--)
            {
                scanf("%d%d%d",&a,&b,&c);
                addedge(a,b,c);
            }
            printf("%d\n",Dinic_flow());
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1532]: http://acm.hdu.edu.cn/showproblem.php?pid=1532