很久前学过增广路算法，今天学习了它的优化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); PRintf("%d",Dinic()); return 0;}新闻热点
疑难解答
