New_hope @ 2023-08-26 21:16:54
#include<bits/stdc++.h>
#define N 205
#define int long long
using namespace std;
struct E {
int ed,c;
};
vector<E> a[N],b[N]; // a 正边,b 反边
queue<int> q;
int n,m,s,t,ans;
int d[N];
bool bfs() {
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(s); d[s] = 1;
while(!q.empty()) {
int fr = q.front(); q.pop();
for(auto j : a[fr]) {
int v = j.ed, c = j.c;
if(!d[v] && c) {
d[v] = d[fr] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int minf) {
if(u == t) return minf;
int sum = 0;
for(int i = 0; i < a[u].size(); i ++) {
int v = a[u][i].ed, w = a[u][i].c;
if(d[v] == d[u]+1 && w) {
int f = dfs(v,min(minf,w));
a[u][i].c -= f;
b[v][i].c += f;
minf -= f;
sum += f;
if(minf <= 0) break;
}
}
if(sum == 0) d[u] = 0;
return sum;
}
signed main() {
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i ++) {
int u,v,w;
cin >> u >> v >> w;
a[u].push_back({v,w});
b[v].push_back({u,0});
}
int Max = 1 << 31;
while(bfs()) {
ans += dfs(s,Max);
}
cout << ans;
return 0;
}
by g1ove @ 2023-08-26 21:19:20
bfs
和 dfs
时正反边都要考虑 建议remake
链式前向星
by g1ove @ 2023-08-26 21:20:43
@New_hope 改的话 a
和 b
算边时都遍历一次
by New_hope @ 2023-08-26 21:22:50
@g1ove 感谢