算法模板（8）：网络流（1）：最大流

• 给定一个包含 $n$ 个点 $m$ 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 $S$ 到点 $T$ 的最大流 ($n\le 1000,m\le 10000,0\le m\le 100000,S\ne T$)

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 20010, INF = 1e8;
int n, m, S, T;
int h[N], f[M], e[M], ne[M], idx;
//d 到当前节点的最小流量，pre 存从哪个边转移过来.
int q[N], d[N], pre[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}bool bfs()
{int hh = 0, tt = 0;memset(st, false, sizeof st);q[0] = S, st[S] = true, d[S] = INF;while(hh <= tt){int u = q[hh++];for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(st[v] || f[i] == 0) continue;st[v] = true;d[v] = min(d[u], f[i]);pre[v] = i;if(v == T) return true;q[++tt] = v;}}return false;
}
int EK()
{int res = 0;while(bfs()){res += d[T];for(int i = T; i != S; i = e[pre[i] ^ 1]){f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];}}return res;
}
int main()
{scanf("%d%d%d%d", &n, &m, &S, &T);memset(h, -1, sizeof h);while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}printf("%d\n", EK());return 0;
}

• 给定一个包含 $n$ 个点 $m$ 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 $S$ 到点 $T$ 的最大流 ($n\le 10000,m\le 100000,0\le c\le 10000,S\ne T$)
• Dinic 算法的优化的地方在于，建立一个分层图（防止环），把能够增广的地方全部增广；第二个优化是当前弧优化，相当于优先“榨干”一条边，“榨干”这条边后再“榨干”下一条边。

#include<bits/stdc++.h>
using namespace std;
const int N = 10100, M = 200010, INF = 1e8;
int n, m, S, T;
int h[N], f[M], e[M], ne[M], idx;
//d 到当前节点的最小流量，pre 存从哪个边转移过来.
int q[N], d[N], cur[N];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}bool bfs()
{//按照所有点到原点的距离建立分层图，并且更新当前弧（即优先榨取的边）memset(d, -1, sizeof d);int hh = 0, tt = 0;q[0] = S, d[S] = 0, cur[S] = h[S];while(hh <= tt){int u = q[hh++];for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(d[v] == -1 && f[i]){d[v] = d[u] + 1;cur[v] = h[v];if(v == T) return true;q[++tt] = v;}}}return false;
}int find(int u, int limit)
{if(u == T) return limit;int flow = 0;for(int i = cur[u]; i != -1 && flow < limit; i = ne[i]){cur[u] = i; //当前弧优化int v = e[i];if(d[v] == d[u] + 1 && f[i]){int t = find(v, min(f[i], limit - flow));if(!t) d[v] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic()
{int res = 0, flow;while(bfs()) while(flow = find(S, INF)) res += flow;return res;
}int main()
{scanf("%d%d%d%d", &n, &m, &S, &T);memset(h, -1, sizeof h);while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}printf("%d\n", dinic());return 0;
}

• 题意：第 $1$ 行有 $2$ 个正整数 $m$ 和 $n$。$m$ 是外籍飞行员数；$n$ 是皇家空军的飞行员总数。外籍飞行员编号为 $1\sim m$；英国飞行员编号为 $m+1\sim n$。接下来每行有 $2$ 个正整数 $i$ 和 $j$，表示外籍飞行员 $i$ 可以和英国飞行员 $j$ 配合。文件最后以 $2$ 个 $-1$ 结束。问最大匹配数以及匹配方案。
• 一个问题和一个网络流问题等价，意味着问题的解集与可行流集合是一一对应的。一个流是否是可行流，判断：（1）流量是否守恒；（2）是否超出容量。
• 用 $Dinic$ 算法求二分匹配最大数，复杂度是 $O(m\sqrt{n})$.

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 5210, INF = 1e8;
int h[N], e[M], ne[M], f[M], idx;int q[N], cur[N], d[N];
int n, m, S, T;//略去 dinic 的模板，只保留建图模板.int main()
{memset(h, -1, sizeof h);scanf("%d%d", &m, &n);S = n + 1, T = n + 2;int a, b;while(cin >> a >> b, a != -1){add(a, b, 1);}for(int i = 1; i <= m; i++) add(S, i, 1);for(int i = m + 1; i <= n; i++) add(i, T, 1);printf("%d\n", dinic());for(int i = 0; e[i ^ 1] != S; i += 2){if(f[i] == 0) printf("%d %d\n", e[i ^ 1], e[i]);}
}

• 题意：假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i(i=1,2,\dots ,m)$。会议餐厅共有 $n$ 张餐桌，每张餐桌可容纳 $c_i(i=1,2,\dots ,n)$ 个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

• 二分图的多重匹配问题，构造一个二分图，源点连向左半部分的图，边的容量是点权；右半部分的图向汇点连边，容量也是点权；左右两部分的结点两两相连，容量为1.
  

// 省去 dinic 模板部分，只保留建图
int main()
{memset(h, -1, sizeof h);scanf("%d%d", &m, &n);S = 0, T = n + m + 1;int tot = 0;for(int i = 1; i <= m; i++){int r;scanf("%d", &r);tot += r;add(S, i, r);}for(int i = m + 1; i <= m + n; i++){int c;scanf("%d", &c);add(i, T, c);}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){add(i, j + m, 1);}}int res = dinic();if(res != tot) printf("0\n");else{printf("1\n");for(int u = 1; u <= m; u++){for(int i = h[u]; i != -1; i = ne[i]){if(m + 1 <= e[i] && e[i] <= m + n && !f[i]){printf("%d ", e[i] - m);}}printf("\n");}}return 0;
}

• 给定一个包含 $n$ 个点 $m$ 条边的有向图，每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
• 建图方式，每条边都减去容量下界；对于每个点，计算容量下界入度之和 $C_{in}$ 和下界出度之和 $C_{out}$，若 $C_{in}>C_{out}$，那么从源点 $S$ 到该点连一条容量为 $C_{in}-C_{out}$ 的边。因为在新图中如果不加这样的边，流量可能不守恒，减去的入流比减去的出流要多，那么把这个多减掉的东西补上去。同理，如果 $C_{in}<C_{out}$，那么就是从当前结点向汇点连一条 $C_{out}-C_{in}$ 的边.
• 当然需要满足从 $S$ 发出的边需要满流，不然不满足流量守恒；同理需要满足到汇点 $T$ 需要满流。不过原图中每一条边都会贡献一个入度和出度。因此在新图中，$S$ 发出的边的容量一定等于汇入 $T$ 的容量，加上从源点流出的流量一定等于流入汇点的流量。因此只要一个满流，另一个一定会满流。

int main()
{memset(h, -1, sizeof h);scanf("%d%d", &n, &m);S = 0, T = n + 1;for(int i = 1; i <= m; i++){int a, b, c, d;scanf("%d%d%d%d", &a, &b, &c, &d);add(a, b, c, d);A[a] -= c, A[b] += c;}int tot = 0;for(int i = 1; i <= n; i++){if(A[i] > 0) add(S, i, 0, A[i]), tot += A[i];else if(A[i] < 0) add(i, T, 0, -A[i]);}if(dinic() != tot) printf("NO\n");else{printf("YES\n");for(int i = 0; i < 2 * m; i += 2){//注意流量要输出反向边printf("%d\n", f[i ^ 1] + l[i]);}}return 0;
}

• 题意：给定一个包含 $n$ 个点 $m$ 条边的有向图，每条边都有一个流量下界和流量上界。给定源点 $S$ 和汇点 $T$，求源点到汇点的最大流。
• 另一种建图方式如下，对于每个点 $v$，建一条从 $S$ 到 $v$ 容量是入度下界之和的边，以及一条从 $v$ 指向 $T$ 容量出度下界之和。然后从 原图的 $t$ 到 $s$ 的一条容量为 $\infty$ 的边，这样子可以保证所有点的流量守恒
• 原图的任意一个可行流，都对应于新图任意一个最大流？证明没懂
  

• 题意：给定一个包含 $n$ 个点 $m$ 条边的有向图，每条边都有一个流量下界和流量上界。给定源点 $S$ 和汇点 $T$，求源点到汇点的最小流。