HDU - 1532 Drainage Ditches （网络流-最大流）

痛定思痛。 2022-06-09 04:39 213阅读 0赞

# 题意： #

题意很明显，是一个典型的最大流问题。运货起始点，序号是1，终点站序号是n 。点代表城市，边代表该段管道所能够承受的最大油流量。求从1->n 的最大运油的总量（一次性）。

输入：边数M，顶点数N

下面M行（起点，终点，该段管道的最大承受流量）

输出：最大的运输量。

#     #

# 这是我的第一个网络流的题目，纪念一下！！！    #

# AC代码：g++ 0ms    #

#include <stdio.h>
    #include <string.h>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    const int INF = 0xfffffff;
    const int MAXN = 200 + 10;
    
    int flow[MAXN][MAXN];//邻接矩阵存放图。（有向图）
    
    //mark[]标记是否访问过，pre[]记录增广路。
    int mark[MAXN], pre[MAXN];
    
    int m, n;
    int f; //f为最大流。
    
    void max_flow() //即 多次BFS
    {
        while(1) {
            memset(mark, 0, sizeof(mark));
            memset(pre, 0, sizeof(pre));
            /********************************* B F S *************/
            queue<int> Q;
            mark[1] = 1;
            Q.push(1);
            while( !Q.empty() ) {
                int cnt = Q.front();
                Q.pop();
                if(cnt == n) {  //找到增广路，跳出。
                    break;
                }
                for(int i = 1; i <= n; i++) {
                    if(!mark[i] && flow[cnt][i] > 0) {
                        mark[i] = 1;
                        Q.push(i);
                        pre[i] = cnt;//如果m点存在于增广路之中，那么pre[m]保存的就是之前的点
                    }
                }
            }
            /**********************************************/
    
            if( !mark[n] ) {  //如果没找到可增广的路，直接跳出.
                break;
            }
            int minx = INF;
            for(int i = n; i != 1; i = pre[i]) {
                minx = min( flow[pre[i]][i], minx );    //沿着能走的路径，逆向找最小值
            }
            for(int i = n; i != 1; i = pre[i]) {
                flow[pre[i]][i] -= minx; //更新正向流量。
                flow[i][pre[i]] += minx; //更新反向流量。
            }
            f += minx;
        }
    }
    
    int main()
    {
        while(scanf("%d %d", &m, &n) != EOF) {
            memset(flow, 0, sizeof(flow));
            for(int i = 1; i <= m; i++) {
                int u, v, len;
                scanf("%d %d %d", &u, &v, &len);
                flow[u][v] += len;//这个题有重边的情况，所以要flow[u][v] += len。
            }                   //原基础上加上重边上的容量,这样能够防止重边
            f = 0;
            max_flow();
            printf("%d\n", f);
        }
        return 0;
    }

参考代码：http://www.cnblogs.com/-hsz/archive/2012/07/24/2605788.html

## 注意事项： ##

本题中，flow\[i\]\[pre\[i\]\] += minx; //更新反向流量。 去掉也对，但是 是因为数据水的原因。同样的题意，你如果把flow\[i\]\[pre\[i\]\] += minx; 去掉，就不对了。比如说（HDU-3549）