zesqwq @ 2022-04-16 10:50:40
#include <bits/stdc++.h>
using namespace std;
const int M = 5005, N = 201;
struct Edge {
int next, to, val;
} edge[M * 2];
struct Pre {
int next, val;
} pre[N];
int h[N], vis[N], n, m, s, t, cnt;
queue<int> q;
void add(int u, int v, int w) {
edge[++cnt] = { h[u], v, w }, h[u] = cnt;
}
bool bfs(int s, int t) {
while (!q.empty())
q.pop();
memset(vis, 0, sizeof(int) * (n + 1));
memset(pre, 0, sizeof(Pre) * (n + 1));
q.push(s);
vis[s] = 1;
int u, v, d;
while (!q.empty()) {
u = q.front(), q.pop();
if (u == t)
return true;
for (int i = h[u]; i; i = edge[i].next) {
v = edge[i].to, d = edge[i].val;
if (d && !vis[v])
pre[v] = { u, i }, q.push(v), vis[v] = 1;
}
}
return false;
}
void read() {
cin >> n >> m >> s >> t;
int l, r, w;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &l, &r, &w);
add(l, r, w);// add(r, l, 0);
}
}
int arg(int s, int t) {
int minn = 0x3f3f3f3f;
// for (int i = t; i != s; i = pre[i].next)
// printf("pre[%d]:{%d %d}", i, pre[i].next, edge[pre[i].val].val);
// puts("");
for (int i = t; i != s; i = pre[i].next)
minn = min(minn, edge[pre[i].val].val);
for (int i = t; i != s; i = pre[i].next)
edge[pre[i].val].val -= minn;// edge[pre[i].val ^ 1].val += minn;
// for (int i = t; i != s; i = pre[i].next)
// printf("pre[%d]:{%d %d}", i, pre[i].next, edge[pre[i].val].val);
return minn;
}
long long EK(int s, int t) {
long long cnt = 0;
while (bfs(s, t)) {
cnt += arg(s, t);
// printf("%lld\n", cnt);
}
return cnt;
}
int main() {
read();
cout << EK(s, t);
return 0;
}
看读入 连反向边都没建 pre的val代表那条边的编号
by rxjdasiwzl @ 2022-04-16 11:30:35
@zhouershan 老问题,数据太水
by rxjdasiwzl @ 2022-04-16 11:30:55
看一下这题之前的讨论区
by 柳下惠 @ 2022-04-16 11:47:14
@zhouershan 这个题不建就跑不过去了
by juruoCms @ 2022-08-13 16:26:15
@zhouershan 啊对对对