很久前學過增廣路算法，今天學習了它的優化Dinic，原理是在dfs前先將殘量網絡用bfs進行分層，dfs時只往下一層搜索，詳細見代碼…… POJ3281 拆點+建圖+網絡流 把每頭牛拆成兩個點，建立超級源點S和匯點T，S->菜->牛->?！?>飲料->匯點。注意不要建重邊?。?！
#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;//到達源點或a=0時沒必要繼續搜 int flow=0,f; for (int& i=cur[t];i!=-1;i=b[i].next)//cur[x]記錄每個節點考慮到的弧，避免重復計算，注意i是引用！??！ { int v=b[i].v; if (d[t]+1==d[v]&&(f=dfs(v,min(a,b[i].cap))>0))//注意括號順序不要搞錯?。?！血的教訓?。。? { 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())//重新構圖 { 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);新聞熱點
疑難解答
