河南萌新联赛2024第（一）场：河南农业大学 C - 有大家喜欢的零食吗

河南萌新联赛2024第（一）场：河南农业大学 C - 有大家喜欢的零食吗

题目描述

在某幼儿园中共有 $n$ 个小朋友，该幼儿园的老师为这 $n$ 个小朋友准备了 $n$ 份不一样的零食大礼包。每个小朋友只能选择一个，但老师并不知道小朋友们喜欢什么类型的零食大礼包，因此，老师让小朋友们分别说出了他们喜欢的零食大礼包都有哪些，老师希望能根据小朋友们的叙述来让所有的小朋友们都能吃到他们喜欢的零食。若并非所有的小朋友都能吃到自己满意的零食，请问老师最少还应购买多少份零食大礼包来保证所有的小朋友都能吃到自己满意的零食。题目保证任意一个小朋友都会喜欢这 $n$ 种大礼包中的至少一种。

输入描述:

输入包含 $n+1$ 行。
第一行一个正整数 $n(1<n<500)$，表示该幼儿园小朋友的数量。
接下来 n 行，每行先给出一个正整数 $k_i$$(1\le k_i<n)$，代表第 $i$ 个小朋友喜欢的零食大礼包的种类数量，然后给出 $k_i$ 个正整数，第 $j(1\le j\le k)$ 个正整数$a_j(1\le a_j\le n)$代表第个小朋友喜欢的零食大礼包的编号。
$($保证每行的 $k_i$ 个正整数不重复，且${\sum }_{i=1}^n{k}_i\le 2\times 10^5)$

输出描述:

若所有的小朋友都能吃到自己喜欢的零食，则输出 “Yes”（不带双引号）；
反之，则在第一行输出“No”（不带双引号），并在第二行输出老师还应购买的零食大礼包的最少的个数。

示例1

输入

3
2 1 2
1 3
3 1 2 3

输出

Yes

说明

根据题目描述和样例，老师可以选择给第一个小朋友1号大礼包，给第二个小朋友3号大礼包，给第三个小朋友2号大礼包。这样可以保证每个小朋友可以吃到自己喜欢的零食。

示例2

输入

3
2 1 2
1 1
2 1 2

输出

No
1

二分图匹配板子题，匈牙利算法求二分图最大匹配。时间复杂度 $O(nm)$，其中 $n$ 为点数，$m$ 为边数。

#include<bits/stdc++.h>  
using namespace std;  

const int N = 510; 

int match[N],g[N][N];
bool vis[N];
int n;

int dfs(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(!vis[i] && g[x][i])
		{
			vis[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				match[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

int Maxmatch()
{
	memset(match,-1,sizeof match);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		if(dfs(i)) ans++;
	} 
	return ans;
}

signed main() 
{  
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	int k;cin>>k;
    	for(int j=1;j<=k;j++)
    	{
    		int x;cin>>x;
    		g[i][x]=1;
		}
	}
    
	int ans=Maxmatch();
	if(ans==n) cout<<"Yes\n";
	else
	{
		cout<<"No\n";
		cout<<n-ans<<"\n";
	}
    
    return 0;
}