YellowBean_Elsa @ 2019-07-08 15:59:36
#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<29);
int n,m,s,t;
int x,y,z,v[200010],w[200010],next[200010],first[20005],tot=1;//tot=-1就会错
int d[20005],maxflow;
queue<int> q;
inline int read(){
int x=0;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return x;
}
inline void add(int x,int y,int z){
v[++tot]=y;w[tot]=z;
next[tot]=first[x];
first[x]=tot;
}
bool bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
d[s]=1;q.push(s);
while(q.size()){
int x=q.front();q.pop();
for(int i=first[x];i;i=next[i]){
int y=v[i];
if(d[y] || !w[i])continue;
d[y]=d[x]+1;
q.push(y);
if(y==t)return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,k,y;
for(int i=first[x];i&&rest;i=next[i]){
if(!w[i] || d[y=v[i]]!=d[x]+1)continue;
k=dinic(y,min(rest,w[i]));
if(!k)d[y]=-1;
w[i]-=k;w[i^1]+=k;
rest-=k;
}
return flow-rest;
}
int main(){
n=read();m=read();s=read();t=read();
for(int i=1;i<=m;i++){
x=read();y=read();z=read();
add(x,y,z);add(y,x,0);
}
int f=0;
while(bfs())
while(f=dinic(s,inf))maxflow+=f;
printf("%d\n",maxflow);
return 0;
}
by yurzhang @ 2019-07-08 16:00:15
方便找反向边
by XeCtera @ 2019-07-08 16:02:10
@YellowBean
for(int i=first[x];i;i=next[i]){
查不到0的
by YellowBean_Elsa @ 2019-07-08 16:09:07
oh! Thanks!
by saipubw @ 2019-07-08 16:13:32
for(int i=first[x];i=-1;i=next[i])
然后你就可以从0开始了……
这点边界问题自己debug一下不久好了
by saipubw @ 2019-07-08 16:14:20
然后你还得把first初始化为-1