BZOJ1711: [Usaco2007 Open]Dingin吃饭
1711: [Usaco2007 Open]Dingin吃饭
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 508 Solved: 259
[Submit][Status]
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
* 第一行: 一个整数,最多可以喂饱的牛数.
Sample Input
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
输入解释:
牛 1: 食品从 {1,2}, 饮料从 {1,2} 中选
牛 2: 食品从 {2,3}, 饮料从 {1,2} 中选
牛 3: 食品从 {1,3}, 饮料从 {1,2} 中选
牛 4: 食品从 {1,3}, 饮料从 {3} 中选
Sample Output
输出解释:
一个方案是:
Cow 1: 不吃
Cow 2: 食品 #2, 饮料 #2
Cow 3: 食品 #1, 饮料 #1
Cow 4: 食品 #3, 饮料 #3
用鸽笼定理可以推出没有更好的解 (一共只有3总食品和饮料).当然,别的数据会更难.
HINT
Source
题解:
比较好想的一道网络流。
如果一头牛可以吃多顿的话就直接在所有可能的组合间连边然后dinic即可
现在牛有了容量限制,自然而然想到把牛拆点,然后就可以解决了。
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 100000 #define maxm 500000 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int n,m,s,t,x,y,maxflow,tot=,a[maxn],b[maxn],head[maxn],cur[maxn],h[maxn],q[maxn]; struct edge{int go,next,v;}e[maxm]; void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;} void insert(int x,int y,int z){ins(x,y,z);ins(y,x,);} bool bfs() { for(int i=s;i<=t;i++)h[i]=-; int l=,r=;q[]=s;h[s]=; while(l<r) { int x=q[++l]; for(int i=head[x];i;i=e[i].next) if(e[i].v&&h[e[i].go]==-) { h[e[i].go]=h[x]+;q[++r]=e[i].go; } } return h[t]!=-; } int dfs(int x,int f) { if(x==t) return f; int tmp,used=; for(int i=head[x];i;i=e[i].next) if(e[i].v&&h[e[i].go]==h[x]+) { tmp=dfs(e[i].go,min(e[i].v,f-used)); e[i].v-=tmp;if(e[i].v)cur[x]=i; e[i^].v+=tmp;used+=tmp; if(used==f)return f; } if(!used) h[x]=-; return used; } void dinic() { maxflow=; while(bfs()) { for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf); } } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();x=read();y=read();
s=;t=*n+x+y+;
for1(i,n)insert(i,i+n,);
for1(i,x)insert(s,*n+i,);
for1(i,y)insert(*n+x+i,t,);
for1(i,n)
{
int xx=read(),yy=read();
for1(j,xx)insert(*n+read(),i,);
for1(j,yy)insert(n+i,*n+x+read(),);
}
dinic();
printf("%d\n",maxflow); return ; }
最新文章
- 如何dos中查看当前MySQL版本信息?
- Linux 小命令
- linux test 命令使用
- iOS - OC NSProcessInfo		系统进程信息
- 第1章 游戏之乐——NIM(1)一排石子的游戏
- yii2源码学习笔记(十七)
- xcode-select: error: tool &#39;xcodebuild&#39; requires Xcode, but active developer directory &#39;/Library/Deve
- MongoDB 重启之后无法连接问题
- php 对问卷结果进行统计
- Iterator(es6)
- [SCOI2009]windy数
- SELinux策略语言--客体类别和许可
- ZooKeeper-配置 zoo.cfg
- 【python-strip】Python strip()方法
- 超级账本Hyperledge的kafka共识算法里的Topic 与 Partition
- bzoj千题计划158:bzoj2406: 矩阵(有源汇上下界可行流)
- UNP学习总结(一)
- 《Android源代码设计模式解析与实战》读书笔记(二十)
- 关于《Java读书笔记》第六章课后习题选择题总结与疑问
- 【Python】Django filter 如何支持 or 条件过滤?