首页 > 代码库 > poj3281 Dining 最大流(奇妙的构图)
poj3281 Dining 最大流(奇妙的构图)
我是按照图论500题的文档来刷题的，看了这题怎么也不觉得这是最大流的题目。这应该是题目做得太少的缘故。
什么是最大流问题？最大流有什么特点？
最大流的特点我觉得有一下几点：
1、只有一个起点、一个终点。如果不是，我们可以构造超级源点，超级汇点。
2、边的容量有上限（有上下限的是另外一种特殊的最大流）。
3、最后求的是一个最大值。
这题可以找到一些影子，一头奶牛只能吃一种食物，喝一种饮料。如果只有一种限制我们能很快反应过来(二分最大匹配），但是两种限制就增加了难度。不过还是可以理解为对边的权值的限制，最后求最大值，就可以网最大流的方向去思考。
怎么建图成了解题的关键。怎么确定一头牛只吃一种食物，只喝一种饮料呢？一种食物被多头牛喜欢，一种饮料也被多头牛喜欢。比较如意理解的是多头牛想喝A饮料，就从这么多头牛（点）连边到A，然后A连一条边出去，边权是1，就决定了，A只能被一头牛选择。
具体的建图：
1、建立一个超级源点，向所有的食物（F个点）连权值都为1的边。超级源点假设是0。
2、从食物向牛连边，权值为1。食物被那头牛喜欢就连一条边。食物的编号为1~F。牛的编号是F+1 ~F+N。
3、牛向牛连边。可以理解为自己向自己连边，权值为1。但是编号不能相同。这就是拆点。这是很关键的一点。可以理解为有两个属性的一一对应，就是食物与饮料是一一对应的。前面的牛是F+1，与之对应的头的编号是F+1+N。
4、建立一个超级汇点，是所有的饮料都连向汇点。汇点编号为F+2*N+D+1。
我的代码在源点和汇点是有出入，源点S不是0，是F+2*N +D+1，汇点的 S+1。主要是SAP的模版习惯下标从1开始。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=410;const int M=2*N*N, INF=0x3f3f3f3f;struct node{ int to,next,w;}edge[M];int head[N],numh[N],h[N],cure[N],pre[N];int ans,tot;void SAP(int s, int e,int n){ int flow,u,tmp,neck,i; ans=0; for(i=1;i<=n;i++) cure[i]=head[i]; numh[0]=n; u=s; while(h[s]<n) { if(u==e) { flow =INF; for(i=s;i!=e;i=edge[cure[i]].to) { if(flow>edge[cure[i]].w) { neck=i; flow =edge[cure[i]].w; } } for(i=s;i!=e;i=edge[cure[i]].to) { tmp=cure[i]; edge[tmp].w-=flow; edge[tmp^1].w+=flow; } ans+=flow; u=neck; } for(i=cure[u];i!=-1;i=edge[i].next) if(edge[i].w && h[u]==h[edge[i].to]+1) break; if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} else { if(0==--numh[h[u]]) break; //GAP优化 cure[u]=head[u]; for(tmp=n,i=head[u];i!=-1;i=edge[i].next) if(edge[i].w) tmp=min(tmp, h[edge[i].to]); h[u]=tmp+1; ++numh[h[u]]; if(u!=s) u=pre[u]; } }}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(pre,-1,sizeof(pre)); memset(h,0,sizeof(h)); memset(numh,0,sizeof(numh));}void addedge(int i,int j,int w){ edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k,a,b,c,s,d,f; while(scanf("%d%d%d",&a,&b,&c)!=EOF) { init(); // 1~b是食物编号，b+1 ~b+2a是牛的编号，b+2a+1 ~ b+2a+c是饮料的编号 s=2*a+b+c+1; n=2*a+b+c+2; for(i=1;i<=b;i++) addedge(s,i,1); for(i=1;i<=a;i++) { scanf("%d%d",&f,&d); for(j=0;j<f;j++) { scanf("%d",&k); addedge(k,b+i,1); } for(j=0;j<d;j++) { scanf("%d",&k); addedge(a+b+i,2*a+b+k,1); } } for(i=b+1;i<=b+a;i++) addedge(i,i+a,1); for(i=2*a+b+1;i<=2*a+b+c;i++) addedge(i,n,1); SAP(s,n,n); printf("%d\n",ans); } return 0;}
poj3281 Dining 最大流(奇妙的构图)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。