网络流模板

2019-11-08 03:07:11

字体：大中小

来源：转载

供稿：网友

#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<algorithm>using namespace std;const int Ni=205;const int MAXN=1000005;struct Edge{ int u,v,c; int next;}edge[20*Ni];int n,m;int edn;//边数int p[Ni];//父亲int d[Ni];int sp,tp;//原点，汇点void addedge(int u,int v,int c){ edge[edn].u=u;edge[edn].v=v;edge[edn].c=c; edge[edn].next=p[u];p[u]=edn++; edge[edn].u=v;edge[edn].v=u;edge[edn].c=0; edge[edn].next=p[v];p[v]=edn++;}int bfs()//构造层次网络{ queue<int> q; memset(d,-1,sizeof(d));//初始化顶点层次为-1 d[sp]=0; q.push(sp); while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=p[cur];i!=-1;i=edge[i].next) { int u=edge[i].v; if(d[u]==-1&&edge[i].c>0)//顶点未被访问过，顶点u，v存在边 { d[u]=d[cur]+1;//给顶点标记层次 q.push(u); } } } return d[tp]!=-1;//返回false表明汇点不在层次网络中}int dfs(int a,int b)//进行增广{ int r=0; if(a==tp) return b; for(int i=p[a];i!=-1&&r<b;i=edge[i].next) { int u=edge[i].v; if(edge[i].c>0&&d[u]==d[a]+1) { int x=min(edge[i].c,b-r); x=dfs(u,x); r+=x; edge[i].c-=x; edge[i^1].c+=x; } } if(!r) d[a]=-2; return r;}int dinic(int sp,int tp)//求出最大流{ int total=0,t; while(bfs()) { while(t=dfs(sp,MAXN)) total+=t; } return total;}int main(){ int i,u,v,c; while(~scanf("%d%d",&m,&n)) { edn=0;//初始化 memset(p,-1,sizeof(p)); sp=1; tp=n; for(i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); } PRintf("%d/n",dinic(sp,tp)); } return 0;}

上一篇：lintcode-简单-落单的数

下一篇：回调函数的定义和使用