BilyHurington @ 2019-05-07 14:16:53
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,x,y,z,head[10010],cnt=-1,dep[10010],cur[10010];
queue<int> q;
struct edge{
int to,dis,nxt;
}e[200010];
void add(int x,int y,int z){
e[++cnt].to=y;
e[cnt].dis=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
bool bfs(){
memset(dep,0,sizeof(dep));
while(!q.empty()) q.pop();
q.push(s);
for(int i=1;i<=n;i++) cur[i]=head[i];
dep[s]=1;
while(!q.empty()){
x=q.front();
q.pop();
for(int i=head[x];i!=-1;i=e[i].nxt){
if(!dep[e[i].to]&&e[i].dis){
dep[e[i].to]=dep[x]+1;
q.push(e[i].to);
}
}
}
if(!dep[t]) return 0;
return 1;
}
int dfs(int x,int minn){
if(x==t||!minn) return minn;
for(int i=cur[x];i!=-1;i=e[i].nxt){
cur[x]=i;
y=dfs(e[i].to,min(minn,e[i].dis));
if(dep[e[i].to]==dep[x]+1&&y){
e[i].dis-=y;
e[i^1].dis+=y;
return y;
}
}
return 0;
}
int dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,2e9);
return ans;
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
add(y,x,0);
}
printf("%d",dinic());
}评测记录
by qsmoonzh @ 2019-05-07 15:08:28
dfs的问题
dinic的dfs
int dfs(int x,int val) {
int fval,ans=0;
if(x==t) return val;
for(int &i=nhead[x]; i; i=e[i].nt)
if(dep[e[i].to]==dep[x]+1&&e[i].v>0) {
fval=dfs(e[i].to,min(val,e[i].v));
e[i].v-=fval;
e[i^1].v+=fval;
val-=fval;
ans+=fval;
if(val==0) break;
}
return ans;
}