網(wǎng)絡(luò)流Dinic

2019-11-09 21:08:05

字體：大中小

供稿：網(wǎng)友

很久前學(xué)過(guò)增廣路算法，今天學(xué)習(xí)了它的優(yōu)化Dinic，原理是在dfs前先將殘量網(wǎng)絡(luò)用bfs進(jìn)行分層，dfs時(shí)只往下一層搜索，詳細(xì)見(jiàn)代碼…… POJ3281 拆點(diǎn)+建圖+網(wǎng)絡(luò)流把每頭牛拆成兩個(gè)點(diǎn)，建立超級(jí)源點(diǎn)S和匯點(diǎn)T，S->菜->牛->?！?>飲料->匯點(diǎn)。注意不要建重邊！??！

#include <cstdio>#include <queue>#include <algorithm>#include <cstring>#define maxn 405#define INF 0x3f3f3fusing namespace std;int d[maxn],n,F,S,D,T,bo2[maxn],bo1[maxn],m,p,q,head[maxn],cur[maxn],x,vis[maxn];struct xx{ int v,next,cap;//cap為殘余流量 }b[maxn*maxn];void add(int u,int v,int q){ b[m]=(xx){v,head[u],q}; head[u]=m++; b[m]=(xx){u,head[v],0}; head[v]=m++;}bool bfs()//分層 { memset(vis,0,sizeof(vis)); queue<int> q; q.push(S); d[S]=0;vis[S]=1; while (!q.empty()) { int u=q.front();q.pop(); for (int k=head[u];k!=-1;k=b[k].next) { int v=b[k].v; if (!vis[v]&&b[k].cap) { vis[v]=1; d[v]=d[u]+1; q.push(v); } } } return vis[T];}int dfs(int t,int a){ if (t==T||a==0) return a;//到達(dá)源點(diǎn)或a=0時(shí)沒(méi)必要繼續(xù)搜 int flow=0,f; for (int& i=cur[t];i!=-1;i=b[i].next)//cur[x]記錄每個(gè)節(jié)點(diǎn)考慮到的弧，避免重復(fù)計(jì)算，注意i是引用！！！ { int v=b[i].v; if (d[t]+1==d[v]&&(f=dfs(v,min(a,b[i].cap))>0))//注意括號(hào)順序不要搞錯(cuò)?。。⊙慕逃?xùn)！??！ { b[i].cap-=f; b[i^1].cap+=f;//反向邊 flow+=f; a-=f; if (a==0) break; } } return flow;}int Dinic(){ int flow=0; while (bfs())//重新構(gòu)圖 { for (int i=0;i<=T;i++) cur[i]=head[i]; flow+=dfs(S,INF); } return flow;}int main(){ scanf("%d%d%d",&n,&F,&D); S=0;T=401;m=0; memset(head,-1,sizeof(head)); for (int i=1;i<=n;i++) { scanf("%d%d",&p,&q); for (int j=1;j<=p;j++) scanf("%d",&x),bo1[x]=1,add(x,i+100,1); for (int j=1;j<=q;j++) scanf("%d",&x),bo2[x]=1,add(i+200,x+300,1); add(i+100,i+200,1); } for (int i=1;i<=F;i++) //避免建重邊 if (bo1[i]) add(S,i,1); for (int i=1;i<=D;i++) if (bo2[i]) add(300+i,T,1);