#1369 : 网络流一·Ford-Fulkerson算法模板题

http://hihocoder.com/problemset/problem/1369?sid=1108721

别人都说先学网络流再学二分图，但是我先学了二分图的，感觉网络流好高端啊。

首先对于原图，e[u][v]，找到一条路径从be --> en后，要更新残余网络。

什么意思，其他东西自己百度。其实就是建反向边。

比如：

1 --> 2 w = 1

1 --> 3 w = 1

2 --> 3 w = 1

2 --> 4 w = 1

3 --> 4 w = 1

那么如果一开始网络流找到的增广路是1-->2-->3-->4后，整个图的最大流就是1，这样就错了。

应该是1-->2-->4和1-->3-->4，最大流是2.所以在2的时候，就要判断它应该流去那里了，如果每种情况都暴力一下，复杂度是指数级。

但是如果建立反向边后，比如找到了1-->2-->3-->4，

则建立

4-->3 w = 1

3-->2 w = 1

2-->1 w = 1

这样做了的话，就可以继续找增广路，可以找到1-->3-->2-->4，贡献是1，

为什么可以这样呢？其实就是相当于把水流回去2那里，让2重新选。

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn =  + ;

int e[maxn][maxn];

int pre[maxn], flow[maxn];

int n, m;

int bfs(int be, int en) {

    queue<int> que;

    memset(pre, false, sizeof pre);

    pre[be] = -, flow[be] = inf;

    que.push(be);

    while (!que.empty()) {

        int id = que.front();

        que.pop();

        if (id == en) break; // 找到增广路径

        for (int i = ; i <= n; ++i) {

            if (pre[i] ==  && e[id][i] > ) {

                pre[i] = id;

                flow[i] = min(flow[id], e[id][i]);

                que.push(i);

            }

        }

    }

    if (pre[en] == ) return -;

    else return flow[en];

}

int maxFlow(int be, int en) {

    int sumFlow = ;

    while (true) {

        int res = bfs(be, en);

        if (res == -) break; //找不到增广路

        int u = pre[en], v = en;

        while (u != -) {

            e[u][v] -= res;

            e[v][u] += res;

            v = u;

            u = pre[v];

        }

        sumFlow += res;

    }

    return sumFlow;

}

void work() {

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; ++i) {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        e[u][v] += w;

    }

    cout << maxFlow(, n) << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

#1369 : 网络流一·Ford-Fulkerson算法模板题

最新文章

热门文章

巴特西

#1369 : 网络流一·Ford-Fulkerson算法 模板题

最新文章

热门文章

#1369 : 网络流一·Ford-Fulkerson算法模板题