首页 > 代码库 > 【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题
【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题
不使用二分图匹配,使用最大流即可,设源点S与汇点T,S->食物->牛->牛->饮料->T,每条边流量为1,因为流过牛的最大流量是1,所以将牛拆成两个点。
前向星,Dinic,复杂度:O(V2E)
直接套用模板
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 30005using namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,F,D,S,f,d,id;bool flag;const int inf = 0x3f3f3f3f;struct edgenode{ int from,to,next; int cap;}edge[MAXM];int Edge,head[MAXN],ps[MAXN],dep[MAXN];void add_edge(int x,int y,int c){ edge[Edge].from=x; edge[Edge].to=y; edge[Edge].cap=c; edge[Edge].next=head[x]; head[x]=Edge++; edge[Edge].from=y; edge[Edge].to=x; edge[Edge].cap=0; edge[Edge].next=head[y]; head[y]=Edge++;}int dinic(int n,int s,int t){ int tr,flow=0; int i,j,k,l,r,top; while(1){ memset(dep,-1,(n+1)*sizeof(int)); for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分,将给定图分层 { for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next) { if (edge[j].cap&&-1==dep[k=edge[j].to]) { dep[k]=dep[i]+1;ps[r++]=k; if(k==t) { l=r; break; } } } } if(dep[t]==-1)break; for(i=s,top=0;;)//DFS部分 { if(i==t)//当前点就是汇点时 { for(k=0,tr=inf;k<top;++k) if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; for(k=0;k<top;++k) edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr; flow+=tr; i=edge[ps[top=l]].from; } for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break; if(j!=-1) { ps[top++]=j;//当前点有所指向的点,把这个点加入栈中 i=edge[j].to; } else { if (!top) break;//当前点没有指向的点,回溯 dep[i]=-1; i=edge[ps[--top]].from; } } } return flow;}int main(){ memset(head,-1,sizeof(head));Edge=0; scanf("%d%d%d",&n,&F,&D); S=0; T=n+n+F+D+1; for (i=1;i<=F;i++) { add_edge(S,2*n+i,1); } for (i=1;i<=D;i++) { add_edge(2*n+F+i,T,1); } for (i=1;i<=n;i++) { scanf("%d%d",&f,&d); add_edge(i,n+i,1); for (j=1;j<=f;j++) { scanf("%d",&id); id=2*n+id; add_edge(id,i,1); } for (j=1;j<=d;j++) { scanf("%d",&id); id=2*n+F+id; add_edge(n+i,id,1); } } printf("%d\n",dinic(T+1,S,T)); return 0;}
【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。