社区讨论
3376 345三个点wa了,求dalao救救蒟蒻
学术版参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi86aea0
- 此快照首次捕获于
- 2025/11/21 09:19 4 个月前
- 此快照最后确认于
- 2025/11/21 09:19 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,inf=1<<29;
int ver[maxn],next[maxn],edge[maxn],tot,head[maxn];
int s,t,n,m,d[maxn],maxflow;
queue<int> q;
void add(int a,int b,int v){
ver[++tot]=b;next[tot]=head[a];head[a]=tot;edge[tot]=v;
ver[++tot]=a;next[tot]=head[b];head[b]=tot;edge[tot]=0;
}
int bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=next[i]){
if(edge[i] and !d[ver[i]]){
q.push(ver[i]);
d[ver[i]]=d[x]+1;
if(ver[i]==t)return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,k;
for(int i=head[x];i and rest;i=next[i]){
if(edge[i] and d[ver[i]]==d[x]+1){
k=dinic(ver[i],min(rest,edge[i]));
if(!k)d[ver[i]]=0;
edge[i]-=k;
edge[i^1]+=k;
rest-=k;
}
}
return flow-rest;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int a,b,v;
scanf("%d%d%d",&a,&b,&v);
add(a,b,v);
}
int flow;
while(bfs()){
while(flow=dinic(s,inf))maxflow+=flow;
}
printf("%d",maxflow);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...