洛谷 P3376 【模板】网络最大流
Description
- 如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
Input
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
Output
- 一行，包含一个正整数，即为该网络的最大流。
Sample Input
4 5 4 34 2 304 3 202 3 202 1 301 3 40
Sample Output
50
Data Size
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
题解：
- 最大流。
- 关于网络流-最大流的学习，我翻了N多篇博客，我也不懂我是从哪一篇学会的，所以这里就不再展开个人的算法讲解。
- 只说说我在学网络流中遇到的一个思维障碍——建反向边。
- 为什么要建方向边，网上大多都是说：因为bfs找到的路径不一定最优，所以建反边是为了给它“反悔”的机会。
- 嘛... ...上述那样说的话我的确感性理解了。也就是说，萌新自欺欺人的话就这样记也行。
- 但是我对建反向边的理由有了个自己的理解：
- 现有一图：（红线为反向边
- 显然，肉眼观察，最大流为15。即5人帮从1 -> 2 -> 4,10人帮从1 -> 3 -> 4。
- 假设第一次bfs找到的路径为1 -> 2 -> 3 -> 4。
- 最大流 += 5(5)，路径上所有边权 -= 5，反向边 += 5，那么图就变成了：
- 即5人帮从1 -> 2 -> 3 -> 4。
- 第二次bfs找到路径1 -> 3 -> 2 -> 4。
- 最大流 += 5(10)，路径上所有边权 -= 5，反向边 += 5，那么图就变成了：
- 这步操作的实际含义是什么呢？即10人帮中派出了5人，他们从1走到3，走到3时，发现曾经有5个人来过这里！他们怎么知道的呢？反向边告诉他们的！于是，他们决定与原5人帮交换灵魂。即原5人帮变成了现在的5个人，现在的5个人变成原5人帮，然后各自继续走对方的道路。
- 那么现在的状况就是：
- 现在的5个人与原5人帮交换灵魂后，继续行走。
- 那其实这种走法不就等价于：
- 5人帮走5人帮的道路，现在的5个人走5个人的道路。
- 第三次bfs找到路径1 -> 3 -> 5
- 最大流 += 5(15)，路径上所有边权 -= 5，反向边 += 5，那么图就变成了：
- 即10人帮中剩下的5个人粗发，当他们走到3时，发现没有人可以灵魂交换。于是便继续走，最终走到了4号点
- 第四次bfs发现走不到4号点了，EK算法结束。
- 至此，我们求出了此图最大流为15。
- 通过上面的解释，相信对为什么要建反边有了一定的理解了。因为，为了使“流”有灵魂交换的机会，从而不会遗漏任何一种情况！
#include#include #include #include #define N 10005#define M 200005#define inf 0x7fffffffusing namespace std;struct Pre {int u, e;} pre[N];struct E {int next, to, dis;} e[M];int n, m, s, t, num = 1;int h[N];bool vis[N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}void add(int u, int v, int w){ e[++num].next = h[u]; e[num].to = v; e[num].dis = w; h[u] = num;}bool bfs(){ memset(vis, 0, sizeof(vis)); pre[s].u = 0; queue que; vis[s] = 1, que.push(s); while(que.size()) { int now = que.front(); que.pop(); for(int i = h[now]; i != 0; i = e[i].next) { int to = e[i].to; if(!vis[to] && e[i].dis) { pre[to].u = now; pre[to].e = i; vis[to] = 1; que.push(to); if(to == t) return 1; } } } return 0;}int EK(){ int ans = 0; while(bfs()) { int Min = inf; for(int i = t; i != s; i = pre[i].u) Min = min(Min, e[pre[i].e].dis); for(int i = t; i != s; i = pre[i].u) e[pre[i].e].dis -= Min, e[pre[i].e ^ 1].dis += Min; ans += Min; } return ans;}int main(){ cin >> n >> m >> s >> t; for(int i = 1; i <= m; i++) { int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, 0); } cout << EK(); return 0;}