首页 > 代码库 > POJ3281:Dining（dinic+拆点）
POJ3281:Dining（dinic+拆点）
题目链接：http://poj.org/problem?id=3281
PS:刷够网络流了，先这样吧，之后再刷，慢慢补。
题意：有F种食物,D种饮料,N头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份),一种食物被一头牛吃了之后,其余牛就不能吃了 第一行有N,F,D三个整数:接着2-N+1行代表第i头牛,前面两个整数是Fi与Di(食物与饮料的种类数量),接着是食物的种类与饮料的种类 要求输出最多分配能够满足的牛的数量.
思路：这是一种神奇的建图方式-拆点。让我想打死都想不出来。sad
建图,有2*n+f+d+2个顶点，0表示源点,2*n+f+d+1表示汇点。 由源点指向食物,再由食物指向牛,牛再指向对应的饮料,饮料再指向汇点 当然要使每一头牛都对应每一份食物与饮料,所以应该牛i指向牛i再指向饮料,这样就可以避免一头牛只占用多份食物与饮料了 全部是有向的边,而且权值全部为1 我在这里是1到f为食物点，f+1到f+2*n为牛点，f+2*n+1到f+2*n+d为饮料点
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>#define N 1100#define inf 0x3f3f3f3ftypedef int ll;using namespace std;ll n,f,d,tt,dis[N],head[N];struct node{ ll x,y,w,next;} eg[N*N];void init(){ tt=0; memset(head,-1,sizeof(head));}void add(int xx,int yy){ eg[tt].x=xx; eg[tt].y=yy; eg[tt].w=1; eg[tt].next=head[xx]; head[xx]=tt++; eg[tt].x=yy; eg[tt].y=xx; eg[tt].w=0; eg[tt].next=head[yy]; head[yy]=tt++;}bool bfs(int s,int e){ memset(dis,-1,sizeof(dis)); dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int fa=q.front(); q.pop(); for(int i=head[fa]; i!=-1; i=eg[i].next) { int v=eg[i].y; if(dis[v]==-1&&eg[i].w) { dis[v]=dis[fa]+1; q.push(v); } } } if(dis[e]>0) return true; return false;}int dinic(int s,int maxt){ if(s==2*n+f+d+1) return maxt; int a,sum=maxt; for(int i=head[s]; i!=-1; i=eg[i].next) { int v=eg[i].y; if(dis[v]==dis[s]+1&&eg[i].w>0) { a=dinic(v,min(sum,eg[i].w)); eg[i].w-=a; eg[i+1].w+=a; sum-=a; } } return maxt-sum;}int main(){ ll xx,yy,s1,s2; scanf("%d%d%d",&n,&f,&d); init(); for(int j=1;j<=f;j++) { add(0,j); } for(int j=1;j<=d;j++) { add(f+2*n+j,f+2*n+d+1); } for(int i=1;i<=n;i++) { scanf("%d%d",&s1,&s2); for(int j=1;j<=s1;j++) { scanf("%d",&xx); add(xx,f+i); } for(int j=1;j<=s2;j++) { scanf("%d",&yy); add(f+n+i,f+2*n+yy); } } for(int i=1;i<=n;i++) { add(f+i,f+n+i); } ll ans=0; while(bfs(0,2*n+f+d+1)) { ans+=dinic(0,inf); } printf("%d\n",ans); return 0;}
POJ3281:Dining（dinic+拆点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。