首页 > 代码库 > BZOJ 1711: [Usaco2007 Open]Dingin吃饭
BZOJ 1711: [Usaco2007 Open]Dingin吃饭
Description
农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料. 农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料. 每一件食物和饮料只能由一头牛来用. 例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2.
Input
* 第一行: 三个数: N, F, 和 D
* 第2..N+1行: 每一行由两个数开始F_i 和 D_i, 分别是第i 头牛可以吃的食品数和可以喝的饮料数.下F_i个整数是第i头牛可以吃的食品号,再下面的D_i个整数是第i头牛可以喝的饮料号码.
Output
* 第一行: 一个整数,最多可以喂饱的牛数.
题解：
最大流。
将牛拆为两个点牛1，牛2。
S向每种饮料连边，每种饮料向被喜欢的牛1连边，牛1向牛2连边，牛2向喜欢的食物连边，每种食物向T连边。
流量均为1。
求S-T最大流即可。
代码:
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<queue>//by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);int n,f;int H[405],tot,S,T,P[160005],flow[160005],X[160005];inline void add(int x,int y,int z){ P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;}int d[405];queue<int> q;bool bfs(){ memset(d,0,sizeof d); d[S]=1; while(!q.empty()) q.pop(); q.push(S); int x; while(!q.empty()){ x=q.front();q.pop(); if(x==T) return 1; for(int i=H[x];i;i=X[i]){ if(flow[i]>0&&!d[P[i]]){ d[P[i]]=d[x]+1; q.push(P[i]); } } } return 0;}int dfs(int x,int a){ if(x==T||a==0) return a; int f=a,tmp; for(int i=H[x];i;i=X[i]){ if(d[P[i]]==d[x]+1&&flow[i]>0){ tmp=dfs(P[i],min(a,flow[i])); a-=tmp; flow[i]-=tmp; flow[i^1]+=tmp; if(!a) break; } } if(f==a) d[x]=-1; return f-a;}int Dinic(){ int f=0; while(bfs()){ f+=dfs(S,inf); } return f;}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif S=403,T=404; tot=1; int d; scanf("%d%d%d",&n,&f,&d); //n 1..n n+1..n+n //f 2*n+1..2*n+f //d 2*n+f+1..2*n+f+d for(int i=1;i<=n;i++){ add(i,i+n,1); add(i+n,i,0); } for(int i=1;i<=f;i++){ add(S,i+2*n,1); add(i+2*n,S,0); } for(int i=1;i<=d;i++){ add(2*n+f+i,T,1); add(T,2*n+f+i,0); } for(int i=1;i<=n;i++){ int fi,di; scanf("%d%d",&fi,&di); int x; for(int j=1;j<=fi;j++){ scanf("%d",&x); add(x+2*n,i,1); add(i,x+2*n,0); } for(int j=1;j<=di;j++){ scanf("%d",&x); add(i+n,x+2*n+f,1); add(x+2*n+f,i+n,0); } } printf("%d\n",Dinic()); return 0;}
BZOJ 1711: [Usaco2007 Open]Dingin吃饭
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。