题目链接
题意：很直白，就是告诉你一个图，求源点1到汇点m的最大流
思路：
模板题，我用的EK，就是不断地在残余网络中找增广路，直到找不出增广路为止。
增广路：
就是从源点到汇点能增加流量的路径。
残余网络：在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”
ac代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
#define int long long
const int maxn = 205;
int cnt[maxn][maxn];
int flow[maxn];
int pre[maxn];
int inf = 0x7f7f7f7f;
queue<int> k; int n, m;
int bfs(int a, int b) {//bfs求增广路流量while (!k.empty()) k.pop();memset(pre, 0, sizeof(pre));k.push(a); pre[a] = -1; flow[a] = inf;while (!k.empty()) {int ll = k.front(); k.pop();if (ll == b) break;for (int i = 1; i <= m; i++) {if (cnt[ll][i] > 0 && pre[i] == 0 && i != a) {pre[i] = ll;flow[i] = min(cnt[ll][i], flow[ll]);k.push(i);}}}if (pre[b] == 0) return -1;return flow[b];
}
int EK(int s, int t) {int tot = 0, mm = 0;while (1) {mm = bfs(s, t);if (mm == -1) break;tot += mm;int p = t;while (p != s) {//反向边更新cnt[p][pre[p]] += mm;cnt[pre[p]][p] -= mm;p = pre[p];} }return tot;
}
signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m) {memset(cnt, 0, sizeof(cnt));memset(flow, 0, sizeof(flow));for (int i = 0; i < n; i++) {int u, v, w; cin >> u >> v >> w;cnt[u][v] += w;}int ans=EK(1, m);cout << ans << endl;}
}