对着置顶题解写的,可是那篇题解 100ms 不到,我的都跑 1s 左右。
都快改得一模一样了,可是越改越慢
#include <bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 205;
const int M = 5e3 + 5;
const LL inf = 1e18;
int n, m, s, t;
LL ans;
int tot = 1, head[N];
struct edge { int nxt, v; LL w; } e[M << 1];
void Addedge(int u, int v, int w) {
e[++tot] = {head[u], v, w};
head[u] = tot;
return ;
}
int now[N];
LL dis[N];
bool Bfs() {
F(i, 1, n) dis[i] = inf;
queue<int> q;
q.push(s);
dis[s] = 0;
now[s] = head[s];
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if (w > 0 && dis[v] == inf) {
dis[v] = dis[u] + 1;
now[v] = head[v];
if (v == t) return 1;
q.push(v);
}
}
}
return 0;
}
LL Dfs(int u, LL sum) {
if (u == t) return sum;
LL res = 0, r;
for (int i = now[u]; i; i = e[i].nxt) {
now[u] = i;
int v = e[i].v;
if (e[i].w > 0 && dis[v] == dis[u] + 1) {
r = Dfs(v, min(sum, e[i].w));
if (!r) dis[v] = inf;
e[i].w -= r;
e[i ^ 1].w += r;
res += r;
sum -= r;
}
}
return res;
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> s >> t;
F(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
Addedge(u, v, w);
Addedge(v, u, 0);
}
while (Bfs()) ans += Dfs(s, inf);
cout << ans;
return 0;
}