求最大流的正常方法
使用層次圖思想,一次增廣多條路,效率大大提高
參考部落格:網絡流-最大流
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxe=,INF=;
int n,e,S,T;
int tot,lnk[maxn],nxt[maxe],cap[maxe],flw[maxe],son[maxe];
void add(int x,int y,int w){
son[++tot]=y;cap[tot]=w;flw[tot]=;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline int red(){
int tot=,f=;char ch=getchar();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=getchar();}
while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
return tot*f;
}
int d[maxn],pos[maxn],que[maxn];
bool bfs(){
memset(d,,sizeof(d));
int hed=,til=;
d[S]=;que[]=S;
while (hed!=til)
for (int j=lnk[que[++hed]];j;j=nxt[j])
if (d[son[j]]==INF&&flw[j]<cap[j])
que[++til]=son[j],d[son[j]]=d[que[hed]]+;
return d[T]!=INF;
}
int dfs(int x,int flow){
if (x==T||flow==) return flow;
int res=,f;
for (int &j=pos[x];j;j=nxt[j])
if (d[x]+==d[son[j]]&&(f=dfs(son[j],min(flow,cap[j]-flw[j])))>){
flw[j]+=f;flw[j^]-=f;
res+=f;flow-=f;
if (flow==) break;
}
return res;
}
int main(){
n=red(),e=red();S=;T=n;tot=;
for (int i=,x,y,z;i<=e;i++)
x=red(),y=red(),z=red(),add(x,y,z),add(y,x,);
int ans=;
while (bfs()){
memcpy(pos,lnk,sizeof(lnk));
ans+=dfs(S,INF);
}
printf("%d",ans);
return ;
}