网络最大流
题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入输出格式
输入格式：第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式：一行，包含一个正整数，即为该网络的最大流。
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
样例说明：
题目中存在3条路径：
4-->2-->3，该路线可通过20的流量
4-->3，可通过20的流量
4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）
故流量总计20+20+10=50。输出50。
原本不打算看网络流，下午帮沈爷爷debug的时候顺便学了一下。
这里写的是DINIC算法。
大概分为BFS 和 DFS 两部分。
BFS主要是用来给图来分层，就是存一下每个点的深度。
代码如下：
1 queue<ll>qq;
2 bool bfs() {
3
4 while(!qq.empty()) qq.pop();
5 memset(dep,0,sizeof(dep));
6 dep[s] = 1;
7 qq.push(s);
8 while(!qq.empty()) {
9 ll u = qq.front();
10 qq.pop();
11 for(int i = head[u]; ~i ; i = e[i].nxt) {
12 if(e[i].c and dep[e[i].v] == 0) {
13 dep[e[i].v] = dep[u] + 1;
14 qq.push(e[i].v);
15 }
16 }
17 }
18 return dep[t];
19 }
而DFS就是来寻找增广路了。就是从源点来走，尽量将所有能走的边都走完。
代码如下：
1 ll dfs(ll nd, ll val) {
2 if(val == 0) return 0;
3 if(nd == t) return val;
4 for(int i = head[nd] ; ~i ; i = e[i].nxt) {
5 ll u = e[i].v;
6 if(dep[u] == dep[nd] + 1 and e[i].c) {
7 ll k = dfs(u , min(e[i].c,val));
8 if(k) {
9 e[i].c -= k;
10 e[i ^ 1].c += k;
11 return k;
12 }
13
14 }
15 }
16 return 0;
17 }
经过我一下午的debug经验，这里重点强调一个问题
存反向边的时候，因为我们存边的时候是需要编号的，而且我们需要尽量快的找到反向边。所以我们在这里设e [ i ]为原有流量，设e [ i ^ 1 ] 为反向边的流量。
但是这里就有问题了。如果我们第一个存下的边的编号设为 1 的话，那我们第一条边的反向边就是0了，而我们这样就返回不到第0条边。
同样，我们在遍历边的时候，我们就不能写成 for （ int i = head[ u ] ; i ; i = e[ i ]. nxt）了；
就必须写成for( ; i>=0 ; ) 或者 for( ; ~i ; )。
同样我们在存边的时候需要预处理一下head数组，初值最好设为-1， 否则会死循环。
完整代码如下：
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #include<cstring>
5 #include<vector>
6 #include<queue>
7 #include <iostream>
8 using namespace std;
9 typedef long long ll;
10 const ll maxn = 1e6 + 7;
11 #define inf 2147483647
12 ll read() {
13 ll a = 0, b = 1;
14 char c = getchar();
15 while(c < \'0\' or c > \'9\') {
16 if(c == \'-\') b = -1;
17 c = getchar();
18 }
19 while(c >= \'0\' and c <= \'9\') {
20 a = a * 10 + c - \'0\';
21 c = getchar();
22 }
23 return a * b;
24 }
25 ll dep[maxn],w[maxn],cnt = -1,n,m,s,ans,t,head[maxn];
26 struct node {
27 ll v,c,nxt;
28 } e[maxn];
29 void add(ll ai, ll bi, ll ci) {
30 e[++cnt].v = bi;
31 e[cnt].c = ci;
32 e[cnt].nxt = head[ai];
33 head[ai] = cnt;
34 }
35 queue<ll>qq;
36 bool bfs() {
37
38 while(!qq.empty()) qq.pop();
39 memset(dep,0,sizeof(dep));
40 dep[s] = 1;
41 qq.push(s);
42 while(!qq.empty()) {
43 ll u = qq.front();
44 qq.pop();
45 for(int i = head[u]; ~i ; i = e[i].nxt) {
46 if(e[i].c and dep[e[i].v] == 0) {
47 dep[e[i].v] = dep[u] + 1;
48 qq.push(e[i].v);
49 }
50 }
51 }
52 return dep[t];
53 }
54 ll dfs(ll nd, ll val) {
55 if(val == 0) return 0;
56 if(nd == t) return val;
57 for(int i = head[nd] ; ~i ; i = e[i].nxt) {
58 ll u = e[i].v;
59 if(dep[u] == dep[nd] + 1 and e[i].c) {
60 ll k = dfs(u , min(e[i].c,val));
61 if(k) {
62 e[i].c -= k;
63 e[i ^ 1].c += k;
64 return k;
65 }
66
67 }
68 }
69 return 0;
70 }
71 int main() {
72 n = read();
73 m = read();
74 s = read();
75 t = read();
76 memset(head,-1,sizeof(head));
77 for(int i=1; i<=m; i++) {
78 ll t1,t2,t3;
79 t1 = read();
80 t2 = read();
81 t3 = read();
82 add(t1,t2,t3);
83 add(t2,t1,0);
84 }
85 while(bfs()) {
86 while(1) {
87 int d = dfs(s,inf);
88 if(d == 0) break;
89 else ans += d;
90 }
91 }
92 printf("%lld\n",ans);
93 return 0;
94 }