JZOJ 2308. 【中山市选2011】聚会

题目

Description

　　Tzdin想组织一个圣诞晚会。N位女士和M位男士（M>=N）会被邀请参加这个聚会。在聚会的开始，Tzdin会派发一些写着某位男士信息的卡片给每位女士；每位女士都会收到若干张这种卡片。然后每位女士可以从她收到的卡片里挑选一位男士作为她的伴侣。我们可以认为经过Tzdin的引导，每位女士都一定可以挑选到一位男士作为他的伴侣，而每位男士最多成为1位女士的伴侣。Tzdin想知道的是，有哪些男士，无论女士们怎么选择，最终都一定会拥有伴侣。

 

Input

　　第一行包括2个正整数N和M。
　　接下来有N行。对于1<=i<=N，有：在第i+1行中，第一个整数k，代表第i位女士收到了k张卡片；接下来有k个正整数，代表的是每张卡片上对应的男士的编号。
　　女士和男士的编号分别是从1到N和1到M。

Output

　　输出若干行，每行为一个整数，代表某位男士的编号；那位男士必须是一定会拥有伴侣的客人。请按照从小到大的顺序输出他们的编号。

 

Sample Input

2 3
1 1
2 2 3

Sample Output

1

 

Data Constraint

 

 

Hint

【数据范围】
　　对20%的数据，有N,M<=10；
　　对40%的数据，有N,M<=100；
　　对100%的数据，有N,M<=1000。

 

分析

• 因为每个女生一定能找到男生

• 所以我们可以跑一遍最大匹配，先找男生与女生相配关系
• 然后我们枚举男生查找如果没了这个男生，那么这个女生是否还能找到另一个

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector> 
using namespace std;
vector <int> f[1001];
int ans[1001];
bool vis[1001];
int link[1001],g[1001];
bool find(int x)
{
    for (int i=0;i<f[x].size();i++)
    {
        int y=f[x][i];
        if (!vis[y])
        {
            vis[y]=true;
            int q=link[y];
            link[y]=x;
            if (q==0||find(q)) return true;
            link[y]=q;
        }
    }
    return false;
}
int main ()
{
    int n,m;
    cin>>n>>m;
    for (int i=1,k;i<=n;i++)
    {
        cin>>k;
        for (int j=1,x;j<=k;j++)
        {
            cin>>x;
            f[i].push_back(x);
        }
    }
    for (int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        find(i);
    }
    memcpy(g,link,sizeof link);
    for (int i=1;i<=m;i++)
    {
        if (g[i])
        {
            memset(vis,0,sizeof(vis));
            vis[i]=1;
            memcpy(link,g,sizeof g);
            if (!find(link[i])) cout<<i<<endl;
        }
    }
}