有大家喜欢的零食吗

题目描述

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

题目保证任意一个小朋友都会喜欢这 n 种大礼包中的至少一种。

一道很普通的关于匈牙利算法的题

左侧有n个小朋友，右侧有n个大礼包，进行二分图配对，如果有n个配对成功，就输出"Yes"不然就输出"No"和未配对成功的数；

bool find(int x)
{
    for (int i = h[x];i != -1;i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }    return false;
  	/*match[j]存的是礼包j对应的小朋友，find函数则是查找x喜欢的大礼包是不是还在，如果还在，则两者配对，如果不在，就看看
    喜欢礼包j的小朋友是不是还有别的喜好，如果有就把礼包j让给x小朋友，自己去找备胎（bushi）主打一个谦让（博爱）*/
}

ac代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int idx, e[N], ne[N], h[N], match[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool find(int x)
{
    for (int i = h[x];i != -1;i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        for (int j = 0; j < x; ++j) {
            int y;
            cin >> y;
            add(i+1, y);
        }
    }
    int res = 0;
    for (int i = 1;i <= n;i++)
    {
        memset(st, false, sizeof st);
        if (find(i))
            res++;
    }
    if (res == n)
        cout << "Yes" << endl;
    else cout << "No" << endl << n - res << endl;
    return 0;
}

纪念我人生的第一次博客