首页 技术 正文
技术 2022年11月24日
0 收藏 480 点赞 4,398 浏览 4013 个字

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbmlrZTBnb29k/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast” style=”font-family:宋体”>

Language:
DefaultDining

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 9631   Accepted: 4446

Description

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.

Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink
a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.

Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

Input

Line 1: Three space-separated integers: NF, and D 

Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers
denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

Output

Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes

Sample Input

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

Sample Output

3

Hint

One way to satisfy three cows is: 

Cow 1: no meal 

Cow 2: Food #2, Drink #2 

Cow 3: Food #1, Drink #1 

Cow 4: Food #3, Drink #3 

The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

Source

field=source&key=USACO+2007+Open+Gold” style=”text-decoration:none”>USACO 2007 Open Gold

首先s向食物连边。饮料向t连边。容量=1(每份食物仅仅有一份)

然后相应的食物向牛。再向相应的饮料连边,容量=1,表示1种取法

可是一仅仅牛仅仅能取一份,所以牛代表的点本身容量=1。故拆点。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXn (100+10)
#define MAXf (100+10)
#define MAXd (100+10)
#define MAXN (1000+10)
#define MAXM ((30300)*2+100)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
class Max_flow //dinic+当前弧优化
{
public:
int n,s,t;
int q[10000];
int edge[MAXM],next[MAXM],pre[MAXN],weight[MAXM],size;
void addedge(int u,int v,int w)
{
edge[++size]=v;
weight[size]=w;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}
bool b[MAXN];
int d[MAXN];
bool SPFA(int s,int t)
{
For(i,n) d[i]=INF;
MEM(b)
d[q[1]=s]=0;b[s]=1;
int head=1,tail=1;
while (head<=tail)
{
int now=q[head++];
Forp(now)
{
int &v=edge[p];
if (weight[p]&&!b[v])
{
d[v]=d[now]+1;
b[v]=1,q[++tail]=v;
}
}
}
return b[t];
}
int iter[MAXN];
int dfs(int x,int f)
{
if (x==t) return f;
Forpiter(x)
{
int v=edge[p];
if (weight[p]&&d[x]<d[v])
{
int nowflow=dfs(v,min(weight[p],f));
if (nowflow)
{
weight[p]-=nowflow;
weight[p^1]+=nowflow;
return nowflow;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(SPFA(s,t))
{
For(i,n) iter[i]=pre[i];
int f;
while (f=dfs(s,INF))
flow+=f;
}
return flow;
}
void mem(int n,int s,int t)
{
(*this).n=n;
(*this).t=t;
(*this).s=s; size=1;
MEM(pre)
}
}S; int n,f,d;
int main()
{
//freopen("poj3281.in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>f>>d;
int s=1,t=2+2*n+f+d;
S.mem(t,1,t);For(i,f)
S.addedge2(s,1+i,1); For(i,d)
S.addedge2(1+f+2*n+i,t,1); For(i,n)
{
S.addedge2(1+f+i,1+f+n+i,1);
int fi,di,p;
scanf("%d%d",&fi,&di);
For(j,fi)
{
scanf("%d",&p);
S.addedge2(1+p,1+f+i,1);
}
For(j,di)
{
scanf("%d",&p);
S.addedge2(1+f+n+i,1+f+2*n+p,1);
} }cout<<S.max_flow(s,t)<<endl;return 0;
}

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,184
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,644
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,488
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,260
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,897
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,062