// 此博文为迁移而来，写于2015年2月6日，不代表本人现在的观点与看法。原始地址：http://blog.sina.com.cn/s/blog_6022c4720102vrg4.html
UPDATE（20180805）：重新看自己的博客，大部分内容还是接受了，但看到这一篇还是不能忍了。。。当年讲的还是太含糊了，怕是本身也没搞得太清楚。但本着基本保持博文原貌的原则，所以我觉得可能重开一篇会更好。链接附上：https://www.cnblogs.com/jinkun113/p/9427825.html
今天我们来谈谈网络流之Dinic算法。这种算法相比Edmond-Karp算法，更加快速，更加常用。还记得EK吗？每次为了防止流量堵塞，必须进行多次BFS/DFS，非常费时间。而Dinic大叔非常机智的发明了Dinic算法，让这个问题得以解决。
Dinic的核心内容是：反复进行BFS绘制出层次图，和DFS进行增广。所谓的层次图就是什么呢？ 从源点到当前点的最近距离，可以存储到一个数组dep中。如图所示，这张图上，dep[1]=0，dep[2]=2，dep[3]=2，dep[4]=1。
而层次图有什么用呢？1、在DFS增广时，当且仅当下一个点的层次是当前点的下一层才进入下一个点；2、是用来判断源点到汇点是否还有流量可以流。如果汇点已经不再层次图上了，说明没有多余的流量可以从源点流到汇点了，这个时候就可以结束搜索而输出答案了。
那么每进行完一次BFS，dep数组要清空。接下来的步骤就和EK算法一个意思了，但是正如*所说，这个是需要设置反向弧使流量可以顺利流走。找出当前增广路的最小流量，到汇点后将本增广路的所有子路减去该流量，且所有反向弧增加该流量。如图所示：
// 原图已经丢失，无法进行迁移
代码如下：
UPDATE（20180805）：全新的代码。
#include <cstdio>
#include <cstring> #define MAXN 205
#define MAXM 205
#define INF 0x3f3f3f3f int m, n, u, v, f, q[MAXN * MAXN], h[MAXN], d[MAXN], o, ans; struct Edge {
int v, next, f;
} e[MAXM << ]; int min(int a, int b) {
return a < b ? a : b;
} void add(int u, int v, int f) {
o++, e[o] = (Edge) {v, h[u], f}, h[u] = o;
} bool BFS() {
int head = , tail = ;
q[] = , d[] = ;
while (head != tail) {
int o = q[head];
for (int x = h[o]; x; x = e[x].next) {
int v = e[x].v;
if (!d[v] && e[x].f > ) d[v] = d[o] + , q[tail++] = v;
}
head++;
}
return d[n] != ;
} int DFS(int o, int mif) {
int res = ;
if (mif <= || o == n) return mif;
for (int x = h[o]; x; x = e[x].next) {
int v = e[x].v;
if (d[v] == d[o] + ) {
int of = DFS(v, min(mif, e[x].f));
e[x].f -= of, e[x + ].f += of, mif -= of, res += of;
if (!mif) break;
}
}
return res;
} int main() {
scanf("%d %d", &m, &n);
for (int i = ; i <= m; i++) scanf("%d %d %d", &u, &v, &f), add(u, v, f), add(v, u, );
while (BFS()) ans += DFS(, INF), memset(d, , sizeof(d));
printf("%d", ans);
return ;
}