【Poj3281】Dining

来源和评测点

USACO 2007 Open Gold
Poj3281
Caioj1116

题目

【题目大意】
有F(1≤F≤1000)块不同的肉(编号1~F)和D(1≤D≤1000)罐不同的饮料(编号1~D),N(1≤N≤1000)头(编号1~N)。
每头牛有自己喜欢的肉和饮料。每块肉和每罐饮料只能供给一头牛使用。
求最多能满足多少头牛能同时享用到自己喜欢的肉和饮料。
(注意某头牛得到满足,不要求享用自己所有喜欢的肉和饮料,
只要喜欢的肉的其中一块和自己喜欢的饮料其中一罐就可以算满足)
【输入格式】
第一行:三个整数N,F,D
接下来N行。每行描述一头牛。
每行开头两个整数Fi和Di,Fi表示该牛喜欢的肉的数目,Di表示它喜欢的饮料的数目。
接下来Fi个数,各表示它喜欢的肉的编号,再来Di个数,表示它喜欢的饮料的编号。
(注意Fi和Di有可能为0)
【输出格式】
一个整数,最大满足的牛的数目
【输入样例】
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
【输出样例】
3

分析

网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他网络流题目参见:Tag-网络流

类似模板题
终极起点连接肉
肉连接牛
牛连接饮料
饮料连接终极终点

但还要拆点,为了让一头牛只能选一种,把一头牛分成两个,自己连自己

所有边权都是1,这样的最大流就是方案数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
const int MAXN=5000,MAXM=1000000;
struct pt
{
int h;
int hou;
}p[MAXN];
struct edge
{
int y,c,g;
int oth;
}e[2*MAXM];
int ln;
void ins(int x,int y,int c)
{
e[++ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
e[++ln].y=x;e[ln].c=0;
e[ln].g=p[y].hou;p[y].hou=ln;
e[ln-1].oth=ln;e[ln].oth=ln-1;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
for(int i=1;i<=ed;i++) p[i].h=0;
lst[1]=st;p[st].h=1;
int tou=1,wei=1;
while(tou<=wei)
{
int x=lst[tou];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==0 and e[k].c>0)
{
p[y].h=p[x].h+1;
lst[++wei]=y;
}
}
tou++;
}
return p[ed].h>0;
}
int dfs(int x,int f)
{
if(x==ed) return f;//debug
int t=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[x].h+1==p[y].h and e[k].c>0 and t<f)
{
int s=dfs(y,mymin(f-t,e[k].c));
t+=s;e[k].c-=s;e[e[k].oth].c+=s;
}
}
if(t==0) p[x].h=0;//debug
return t;
}
/*
1~f
f+1~f+n
f+n+1~f+n+n
f+n+n+1~f+n+n+d
*/
int main()
{
int n,f,d;scanf("%d%d%d",&n,&f,&d);
int cw1=f,cw2=f+n,dk=f+n+n;
st=f+n+n+d+1,ed=f+n+n+d+2;
ln=0;
for(int i=1;i<=n;i++)
{
int fi,di;scanf("%d%d",&fi,&di);
for(int j=1;j<=fi;j++)
{
int t;scanf("%d",&t);
ins(t,cw1+i,1);
}
for(int j=1;j<=di;j++)
{
int t;scanf("%d",&t);
ins(cw2+i,dk+t,1);
}
ins(cw1+i,cw2+i,1);
}
for(int i=1;i<=f;i++) ins(st,i,1);
for(int i=1;i<=d;i++) ins(dk+i,ed,1);
int ans=0;
while(bfs()) ans+=dfs(st,INF);
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/6d11.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%