Tjaweiof @ 2023-12-27 21:22:50
RT,提交记录
#include <bits/stdc++.h>
using namespace std;
int fl[201], wlevel[201][201];
pair <int, int> wraw[201][201];
vector <int> raw[201], level[201];
void make(int s){
memset(fl, 0, sizeof fl);
for (int i = 1; i <= 200; i++){
level[i].clear();
}
queue <int> q;
q.push(s);
while (!q.empty()){
int u = q.front();
q.pop();
for (auto v : raw[u]){
if (wraw[u][v].second && !fl[v]){
q.push(v);
fl[v] = fl[u] + 1;
level[u].push_back(v);
wlevel[u][v] = wraw[u][v].second;
}
}
}
return;
}
int dfs(int x, int t, int ans){
if (x == t){
return ans;
}
if (fl[x] >= fl[t]){
return 0;
}
int res = 0;
for (auto u : level[x]){
if (wlevel[x][u]){
int d = dfs(u, t, min(ans, wlevel[x][u]));
res += d;
wraw[x][u].second -= d;
}
}
return res;
}
int dinic(int s, int t){
int ans = 0;
while (true){
make(s);
if (!fl[t]){
break;
}
ans += dfs(s, t, 2147483647);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, s, t, u, v, w;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++){
cin >> u >> v >> w;
raw[u].push_back(v);
wraw[u][v] = {w, w};
}
cout << dinic(s, t);
return 0;
}
by keep_of_silence @ 2023-12-28 08:13:15
@Tjaweiof 网络流要建双向边
by Tjaweiof @ 2023-12-28 12:09:35
@keep_of_silence 感谢