挪威的森林 @ 2019-09-23 15:29:41
/*
与ek算法有异曲同工之妙,ek太过暴力。
dinic是将ek分层之后再搞。
bfs用于建图,dfs用于增广(一层就一个了)。
*/
#include<bits/stdc++.h> //存反向边,异或一下
using namespace std; const int maxn = 1e5+10;
const int inf=1e9+7;
struct node{
int to,nx,we;
}s[maxn<<2]; int head[maxn>>2],cnt=1,dep[maxn>>2];
int n,m,st,en;
void add(int u,int v,int w){
s[++cnt].to=v;s[cnt].nx=head[u];head[u]=cnt;s[cnt].we=w;
}
int bfs(int st,int en){
// memset(dep,0,sizeof(dep));
for(int i=1;i<=n;i++) dep[i]=0;
queue<int> q;
q.push(st);
dep[st]=1;
while(!q.empty()){
int t=q.front(); q.pop();
for(int i=head[t];i;i=s[i].nx){
int to=s[i].to; //边权为0了就不用建图了
//如果再连边的话图形状不会改变,会死循环。
if(s[i].we==0||dep[to]) continue;
dep[to]=dep[t]+1;
q.push(to);
}
}
if(dep[en]) return 1; return 0;
}
int dfs(int u,int v,int mi){
if(u==v||mi==0) return mi;
int res=0;
for(int i=head[u];i;i=s[i].nx){
int to=s[i].to,tmp;
//容量最小值为目前的容量或者其他
if(dep[to]==dep[u]+1&&(tmp=dfs(to,v,min(mi,s[i].we)))){
s[i].we-=tmp;
s[i^1].we+=tmp;
res+=tmp; mi-=tmp; //当前流量减
}
}
return res;
}
void dinic(){
int res=0;
while(bfs(st,en)){ //有增广路就分层后增广
res+=dfs(st,en,inf); //inf表示目前拥有的流量
}
cout<<res<<endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>st>>en;
for(int i=1;i<=m;i++){
int a,b,c; cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dinic();
return 0;
}
by 1saunoya @ 2019-09-23 15:31:58
反向边 为 0
by 挪威的森林 @ 2019-09-25 22:17:01
@清风ღ