参考:
https://blog.csdn.net/txl199106/article/details/64441994
分析：
该算法是用bfs求出是否有路从s到t， 然后建立反向边（关于反向边）， 最终求出答案， 复杂度(mn)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = + ;
const int MAXM = + ;
const int MAX_INT = ( << ); struct Edge {
int v, nxt, w;
}; struct Node {
int v, id;
}; int n, m, ecnt, S , T; // n , m , S , T 点，边，源点，汇点
bool vis[MAXN];
int head[MAXN];
Node pre[MAXN];
Edge edge[ * MAXM]; void init() {
ecnt = ;
memset(edge, , sizeof(edge));
memset(head, -, sizeof(head));
} void addEdge(int u, int v, int w) {
edge[ecnt].v = v;
edge[ecnt].w = w;
edge[ecnt].nxt = head[u];
head[u] = ecnt++;
} bool bfs(int s, int t) {
queue <int> que;
memset(vis, , sizeof(vis));
memset(pre, -, sizeof(pre));
pre[s].v = s;
vis[s] = true;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = head[u]; i + ; i = edge[i].nxt) {
int v = edge[i].v;
if(!vis[v] && edge[i].w) {
pre[v].v = u;
pre[v].id = i;
vis[v] = true;
if(v == t)
return true;
que.push(v);
}
}
}
return false;
} int EK(int s, int t) {
int ans = ;
while(bfs(s, t)) {
int mi = MAX_INT;
for(int i = t; i != s; i = pre[i].v) {
mi = min(mi, edge[pre[i].id].w);
}
for(int i = t; i != s; i = pre[i].v) {
edge[pre[i].id].w -= mi;
edge[pre[i].id ^ ].w += mi; //异或1的用处是 偶数+1， 奇数-1 （两条正反向边是相邻的
}
ans += mi;
}
return ans;
} int main() {
freopen("1.txt","r", stdin);
init();
ios::sync_with_stdio(false);
cin >> n >> m >> S >> T;
for(int i = ; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, );
}
// 调用
cout << EK(S, T) << "\n";
}
// 加边