题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式
第一行包含四个正整数 n nn,m mm,s ss,t tt，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数 ui ,vi,wi ，表示第 i 条有向边从 ui 出发，到达 vi，边权为 wi即该边最大流量为 wi）。
输出格式
一行，包含一个正整数，即为该网络的最大流。
输入输出样例
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40
50
样例输入输出 1 解释
以下代码来源于《算法竞赛入门指南》
在最大流问题中，容量c cc和流量f ff满足三个性质：容量限制，即f ( u , v ) f(u,v)f(u,v) ≤ \leq≤ c ( u , v ) c(u,v)c(u,v)、斜对称性即 f ( u , v ) f(u,v)f(u,v) = − -− f ( v , u ) f(v,u)f(v,u)和流量平衡(对于除了节点s ss 和 节点t tt 外的任意节点u uu，
∑ ( u , v ) ∈ E f ( u , v ) = 0 \sum_{(u,v)\in E}^{} f(u,v) = 0
(u,v)∈E
∑
f(u,v)=0
)。
问题的目标是最大化 ∣ f ∣ |f|∣f∣ =
∑ ( s , v ) ∈ E f ( s , v ) = ∑ ( u , t ) ∈ E f ( u , t ) \sum_{(s,v)\in E}^{} f(s,v) = \sum_{(u,t)\in E}^{} f(u,t)
(s,v)∈E
∑
f(s,v)=
(u,t)∈E
∑
f(u,t)
，即从s ss点流出的净流量（其也等于流入t tt点的净流量）。
算法思想：
从零流（所有边的流量均为0）开始不断增加流量，保持每次增加流量之后，都满足容量限制、斜对称性和流量平衡三个条件。
称每条边上容量与流量之差为残余容量，简称残量
根据下图a aa得到残量网络b bb，同样的可以由c cc得到d dd。
注意残量网络中的边数可能达到原图中的边数的两倍，在原图中：c = 16 c=16c=16,f = 11 f=11f=11的边在残量网络中对应正反两条边，残量分别为16 − 11 = 5 16-11=516−11=5和0 − ( − 11 ) = 11 0-(-11) = 110−(−11)=11
该算法基于这样一个事实：残量网络中任意一条从s ss到t tt的有向道路都对应一条原图中的增广路，只需要求出该道路中所有残量的最小值d dd，把对应的所有边上的流量增加d dd即可，这个过程称为增广过程。如果增广前的流量满足三个条件，增广后依然满足。显然，只要残量网络中存在增广路，流量就可以增大。可以证明他的逆命题也成立：如果残量网络中不存在增广路，则当前流就是最大流。这便是著名的增广路定理
当且仅当残量网络中不存在s ss− -−t tt的有向道路(增广路)时，此时的流时从s ss到t tt的最大流
struct Edge { int u, v; ll cap, flow; Edge(int uu, int vv, ll _cap, ll _flow) { u = uu, v = vv, cap = _cap, flow = _flow; } }; struct EdmondsKarp { ll n, m; vector<Edge> edges; vector<int> G[maxn]; ll a[maxn], p[maxn]; void init(int n) { for (int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void add(int u, int v, ll cap) { edges.push_back(Edge(u, v, cap, 0)); edges.push_back(Edge(v, u, 0, 0)); m = edges.size(); G[u].push_back(m - 2); G[v].push_back(m - 1); } ll maxFlow(int s, int t) { ll Flow = 0; while (true) { memset(a, 0, sizeof a); queue<int> que; que.push(s); a[s] = INF; while (que.size()) { int u = que.front(); que.pop(); for (int i = 0; i < G[u].size(); i++) { int id = G[u][i]; Edge &e = edges[id];///不加&也是可以的 int to = e.v; if (!a[to] && e.cap > e.flow) { p[to] = id; a[to] = min(a[u], e.cap - e.flow); que.push(to); } } if (a[t]) break; } if (!a[t]) break; for (int u = t; u != s; u = edges[p[u]].u) { edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } Flow += a[t]; } return Flow; } } slove; int n, m, s, t; int main() { cin >> n >> m >> s >> t; slove.init(n); slove.n = n; for (int i = 1; i <= m; i++) { int u = read, v = read; ll cap = read; slove.add(u,v,cap); } cout << slove.maxFlow(s,t) <<endl; return 0; }
