// 11135.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。//#include <iostream>#include <queue>#include <memory.h>#include <map>#include <unordered_set>using namespace std;/*给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 S 到点 T 的最大流。输入格式第一行包含四个整数 n,m,S,T。接下来 m 行，每行三个整数 u,v,c，表示从点 u 到点 v 存在一条有向边，容量为 c。点的编号从 1 到 n。输出格式输出点 S 到点 T 的最大流。如果从点 S 无法到达点 T 则输出 0。数据范围2≤n≤1000,1≤m≤10000,0≤c≤10000,S≠T输入样例：7 14 1 71 2 51 3 61 4 52 3 22 5 33 2 23 4 33 5 33 6 74 6 55 6 16 5 15 7 86 7 7输出样例：14*//*4 5 1 41 2 401 4 202 4 202 3 303 4 10//==============50*/const int N = 10010;const int M = 20010;map<pair<int, int>, int> graphW;unordered_set<int> g[N];int n, m;int S, T;int ans = 0;int d[N];int pre[N];int st[N];void addEdge(int from, int to, int flow){ //数组记录两点之间的关系 使用哈希记录两点之间的流 加速查找 pair<int, int> p1 = make_pair(from, to); graphW[p1] += flow; pair<int, int> p2 = make_pair(to, from); graphW[p2] += 0; g[from].insert(to); g[to].insert(from);}bool bfs(){ memset(st, 0, sizeof(st)); queue<int> q; q.push(S); st[S] = 1; d[S] = 100000010; while (q.size()) { int t = q.front(); q.pop(); for (auto ver : g[t]) { pair<int, int> edge = make_pair(t,ver); int f = graphW[edge]; if (!st[ver] && f) { st[ver] = 1; d[ver] = min(d[t], f); pre[ver] = t; if (ver == T) return true; q.push(ver); } } } return false;}int main(){ cin >> n >> m >> S >> T; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; addEdge(a, b, w); } while (bfs()) { ans += d[T]; int from = T; int to = pre[from]; while (1) { pair<int, int> E = make_pair(from, to); pair<int, int> revE = make_pair(to, from); graphW[E] += d[T]; graphW[revE] -= d[T]; if (to == S) break; from = to; to = pre[from]; } } cout << ans << endl; return 0;}作者：itdef链接：https://www.acwing.com/file_system/file/content/whole/index/content/1121865/来源：AcWing著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6  7 const int N = 1010, M = 20010, INF = 1e8; 8  9 int n, m, S, T;10 int h[N], e[M], f[M], ne[M], idx;11 int q[N], d[N], pre[N];12 bool st[N];13 14 void add(int a, int b, int c)15 {16 e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;17 e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;18 }19 20 bool bfs()21 {22 int hh = 0, tt = 0;23 memset(st, false, sizeof st);24 q[0] = S, st[S] = true, d[S] = INF;25 while (hh <= tt)26  {27 int t = q[hh ++ ];28 for (int i = h[t]; ~i; i = ne[i])29  {30 int ver = e[i];31 if (!st[ver] && f[i])32  {33 st[ver] = true;34 d[ver] = min(d[t], f[i]);35 pre[ver] = i;36 if (ver == T) return true;37 q[ ++ tt] = ver;38  }39  }40  }41 return false;42 }43 44 int EK()45 {46 int r = 0;47 while (bfs())48  {49 r += d[T];50 for (int i = T; i != S; i = e[pre[i] ^ 1])51 f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];52  }53 return r;54 }55 56 int main()57 {58 scanf("%d%d%d%d", &n, &m, &S, &T);59 memset(h, -1, sizeof h);60 while (m -- )61  {62 int a, b, c;63 scanf("%d%d%d", &a, &b, &c);64  add(a, b, c);65  }66 67 printf("%d\n", EK());68 69 return 0;70 }71 72 作者：itdef73 链接：https://www.acwing.com/file_system/file/content/whole/index/content/1121865/74 来源：AcWing75 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。