AcWing 1394. 完美牛棚(匈牙利算法)
原题链接
中等
作者:
殇ベ_11
,
2021-05-19 21:40:03
,
所有人可见
,
阅读 668
题目描述
农夫约翰上周刚刚建好了新的牛棚,并引进了最新的挤奶技术。
不幸的是,由于工程问题,牛棚中的每个单间都不太一样。
第一周,约翰将奶牛们随机分配在了各个单间中。
但是很快他就发现,每头奶牛都只愿意在一部分自己喜欢的单间中产奶。
在过去的一周中,农夫约翰一直在收集有关哪些奶牛愿意在哪些单间产奶的数据。
一个单间只能分配给一头奶牛,当然,一头奶牛也可能只愿意在一个单间中产奶。
给定奶牛的住宿喜好,请你计算,通过合理分配奶牛的住所,最多能够让多少奶牛可以住在自己愿意产奶的单间中。
输入格式
第一行包含两个整数 N 和 M,分别表示奶牛的数量以及单间的数量。
接下来 N 行,每行记录一个奶牛愿意产奶的单间信息。首先包含一个整数 Si,表示这头奶牛愿意在 Si 个单间中产奶。接下来包含 Si 个不同的整数,表示这些单间的编号。
所有单间的编号为 1∼M。
输出格式
输出一个整数,表示可以被分配在自己愿意产奶的单间中的奶牛的最大数量。
数据范围
0≤N,M≤200
0≤Si≤M
样例
输入样例:
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
输出样例:
4
算法1
(匈牙利算法)
C++ 代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e4;
int n,m,q;
int head[N],idx;
int match[N];
bool st[N];
struct edge{
int to;
int next;
}e[N];
void add(int u,int v)
{
e[++idx].to = v;
e[idx].next = head[u];
head[u] = idx;
}
int find(int u) // 匈牙利算法
{
for(int i = head[u];i;i = e[i].next)
{
int v = e[i].to;
if(!st[v])
{
st[v] = true;
if(match[v] == 0 || find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
{
int a;
scanf("%d",&a);
while(a--)
{
int u;
scanf("%d",&u);
add(i,u);
}
}
int res = 0;
for(int i = 1;i <= m;i ++){
memset(st, false, sizeof(st));
if(find(i)) res ++;
}
printf("%d",res);
return 0;
}
题解中
for(int i = 1;i <= m;i ){
memset(st, false, sizeof(st));
if(find(i)) res ;
}
的m应该是n,底下这个样例可以卡掉
5 3
0
0
0
1 1
0