社区讨论
网络流EK算法求助,8, 9,10点WA了
P3376【模板】网络最大流参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lodkwcto
- 此快照首次捕获于
- 2023/10/31 08:16 2 年前
- 此快照最后确认于
- 2023/11/06 23:25 2 年前
RT
加了long long的
CPP#include <bits/stdc++.h>
using namespace std;
long long n , m , s , t , ans;
long long pre[210] , dis[210][210] , vis[210] , minn[210];
vector<int> e[210];
bool bfs(){
memset(vis , 0 , sizeof(vis));
queue<int> q;
vis[s] = 1;
q.push(s);
minn[s] = 0x3ffffffffff;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < e[x].size(); i++){
int nx = e[x][i];
if(dis[x][nx]){
if(vis[nx]) continue;
minn[nx] = min(minn[x] , dis[x][nx]);
pre[nx] = x;
q.push(nx);
vis[nx] = 1;
if(nx == t) return 1;
}
}
}
return 0;
}
void update(){
int x = t;
while(x != s){
int px = pre[x];
dis[x][px] += minn[t];
dis[px][x] -= minn[t];
x = px;
}
ans += minn[t];
}
int main(){
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++){
int x , y;
long long z;
cin >> x >> y >> z;
e[x].push_back(y);
dis[x][y] = z;
e[y].push_back(x);
}
while(bfs()) update();
cout << ans;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...