wtcqwq @ 2022-01-24 10:02:42
rt
哪位大佬帮我调一下,非常感谢
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=200009;
const ll N=50009;
struct edge{
ll to,c,nxt;
}e[M*2];
ll flow[N],pre[N];
ll hd[N];
ll S,T,nE=1,n,m;
const ll INF=1e9;
void add(ll u,ll v,ll c){
e[++nE]=(edge){v,c,hd[u]};
hd[u]=nE;
}
bool bfs(){
fill(pre,pre+1+n,0);
queue<ll> q;
q.push(S);
pre[S]=-1;
flow[S]=INF;
while(!q.empty()){
ll u=q.front(); q.pop();
for(int i=hd[u];i;i=e[i].nxt){
ll c=e[i].c;
if(!c)continue;
ll v=e[i].to;
if(pre[v])continue;
q.push(v);
pre[v]=i;
flow[v]=min(flow[u],c);
if(v==T)return 1;
}
}
return 0;
}
void EdmondKarp(){
ll maxFlow=0;
while(bfs()){
maxFlow+=flow[n];
for(int u=T;u!=S;u=e[pre[u]^1].to){
e[pre[u]].c-=flow[T];
e[pre[u]^1].c+=flow[T];
}
}
cout<<maxFlow<<endl;
}
int main(){
cin>>n>>m>>S>>T;
for(int i=1;i<=m;i++){
ll u,v,c;
cin>>u>>v>>c;
add(u,v,c);
add(v,u,0);
}
EdmondKarp();
return 0;
}
by Code_AC @ 2022-01-24 10:09:50
@王韬淳 您会用Dinic吗?您用Dinic吧
by Code_AC @ 2022-01-24 10:12:08
@王韬淳 【模板】网络最大流 您可以看一眼
by wtcqwq @ 2022-01-24 10:15:41
@撤硕____ 哦 我会用Dinic 就是想把其他方法也学一学。不过非常感谢
by Code_AC @ 2022-01-24 10:18:09
@王韬淳 主要是本蒟蒻也不会EK,其实会Dinic就可以了,比EK要好
by wtcqwq @ 2022-01-24 10:28:49
好 谢谢