最大流模板——进阶指南整理

int d[maxn]; bool bfs(){//在残量网络上构造分层图 memset(d,0,sizeof d); queue<int>q; while(q.size())q.pop(); q.push(s);d[s]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(d[y] || e[i].w==0)continue; q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } return 0; } int dfs(int x,int flow){ if (x==t)return flow; int rest=flow; for(int i=head[x];i!=-1 && rest>0;i=e[i].nxt){ int y=e[i].to; if(e[i].w==0 || d[y]!=d[x]+1)continue; int k=dfs(y,min(rest,e[i].w)); if(!k) d[y]=0; //y点已经被增广完毕,本次dinic时不会再访问这个点 e[i].w-=k; e[i^1].w+=k; rest-=k; } return flow-rest; } int flow=0,ans=0; while(bfs()) while(flow=dinic(s,inf)) ans+=flow;

 

转载于:https://www.cnblogs.com/zsben991126/p/10994054.html

相关资源：性能测试进阶指南——LoadRunner11实战 part1