網(wǎng)絡(luò)流模板

2019-11-08 03:07:11

字體：大中小

供稿：網(wǎng)友

#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;//邊數(shù)int p[Ni];//父親int d[Ni];int sp,tp;//原點(diǎn)，匯點(diǎn)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()//構(gòu)造層次網(wǎng)絡(luò){ queue<int> q; memset(d,-1,sizeof(d));//初始化頂點(diǎn)層次為-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)//頂點(diǎn)未被訪問過，頂點(diǎn)u，v存在邊 { d[u]=d[cur]+1;//給頂點(diǎn)標(biāo)記層次 q.push(u); } } } return d[tp]!=-1;//返回false表明匯點(diǎn)不在層次網(wǎng)絡(luò)中}int dfs(int a,int b)//進(jìn)行增廣{ 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); }