Tjaweiof @ 2023-12-29 21:22:44
RT,提交记录
#include <bits/stdc++.h>
using namespace std;
long long fl[201], wlevel[201][201], wraw[201][201];
vector <long long> raw[201], level[201];
bool vis[201];
void make(int s){
memset(fl, 0, sizeof fl);
memset(vis, false, sizeof vis);
for (int i = 1; i <= 200; i++){
level[i].clear();
}
queue <int> q;
q.push(s);
vis[s] = true;
while (!q.empty()){
int u = q.front();
q.pop();
for (auto v : raw[u]){
if (wraw[u][v] && !vis[v]){
q.push(v);
fl[v] = fl[u] + 1;
vis[v] = true;
level[u].push_back(v);
wlevel[u][v] = wraw[u][v];
}
}
}
return;
}
long long dfs(int x, int t, long long ans){
if (x == t){
return ans;
}
if (fl[x] >= fl[t]){
return 0;
}
long long res = 0;
for (auto u : level[x]){
if (wlevel[x][u]){
long long d = dfs(u, t, min(ans, wlevel[x][u]));
res += d;
wraw[x][u] -= d;
if (!wraw[u][x]){
wraw[u][x] += d;
raw[u].push_back(x);
} else {
wraw[u][x] += d;
}
}
}
return res;
}
long long dinic(int s, int t){
long long ans = 0;
while (true){
make(s);
if (!fl[t]){
break;
}
long long d = dfs(s, t, 2147483647);
if (!d){
break;
}
ans += d;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, s, t, u, v;
long long 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;
raw[u].push_back(v);
wraw[u][v] = w;
}
cout << dinic(s, t);
return 0;
}
by Paradise_Lost @ 2023-12-29 21:50:12
@Tjaweiof
没考虑重边,而且你为什么加了两次边?
by Tjaweiof @ 2023-12-30 18:31:09
@Paradise_Lost ?什么加两次边?
by Paradise_Lost @ 2023-12-30 19:00:55
@Tjaweiof
可能是我没看懂你写法,试一下把
wraw[u][v] = w;
改成
wraw[u][v] += w;
by Tjaweiof @ 2023-12-31 06:42:33
@Paradise_Lost 过了,感谢
by Tjaweiof @ 2023-12-31 06:42:53
@Paradise_Lost 已关