#define INF 2000000000 #define typec int//type of cost const int pN=600000,eN=3000000; struct Edge{ int u,v,next; typec w; }; Edge edge[eN]; int en,head[pN],cur[pN],ps[pN],dep[pN]; void insert(int u,int v,typec w){ edge[en].u=u; edge[en].v=v; edge[en].w=w; edge[en].next=head[u]; head[u]=en++; edge[en].u=v; edge[en].v=u; edge[en].w=0;//有向为0,无向为w edge[en].next=head[v]; head[v]=en++; } typec max_flow(int n,int s,int t){ typec tr,res=0; int i,j,k,f,r,top; while(1){ memset(dep,-1,n*sizeof(int)); for(f=dep[ps[0]=s]=0,r=1;f!=r;) for(i=ps[f++],j=head[i];j!=-1;j=edge[j].next){ if(edge[j].w&&-1==dep[k=edge[j].v]){ dep[k]=dep[i]+1; ps[r++]=k; if(k==t){ f=r; break; } } } if(-1==dep[t])break; memcpy(cur,head,n*sizeof(int)); for(i=s,top=0;;){ if(i==t){ for(k=0,tr=INF;k<top;++k) if(edge[ps[k]].w<tr) tr=edge[ps[f=k]].w; for(k=0;k<top;++k) edge[ps[k]].w-=tr,edge[ps[k]^1].w+=tr; res+=tr; i=edge[ps[top=f]].u; } for(j=cur[i];cur[i]!=-1;j=cur[i]=edge[cur[i]].next) if(edge[j].w&&dep[i]+1==dep[edge[j].v])break; if(cur[i]!=-1){ ps[top++]=cur[i]; i=edge[cur[i]].v; }else{ if(0==top)break; dep[i]=-1; i=edge[ps[--top]].u; } } } return res; }