Description

　　Tzdin想組織一個圣誕晚會。N位女士和M位男士（M>=N）會被邀請參加這個聚會。在聚會的開始，Tzdin會派發(fā)一些寫著某位男士信息的卡片給每位女士；每位女士都會收到若干張這種卡片。然后每位女士可以從她收到的卡片里挑選一位男士作為她的伴侶。我們可以認(rèn)為經(jīng)過Tzdin的引導(dǎo)，每位女士都一定可以挑選到一位男士作為他的伴侶，而每位男士最多成為1位女士的伴侶。Tzdin想知道的是，有哪些男士，無論女士們怎么選擇，最終都一定會擁有伴侶。

Input

　　第一行包括2個正整數(shù)N和M。
　　接下來有N行。對于1<=i<=N，有：在第i+1行中，第一個整數(shù)k，代表第i位女士收到了k張卡片；接下來有k個正整數(shù)，代表的是每張卡片上對應(yīng)的男士的編號。
　　女士和男士的編號分別是從1到N和1到M。

Output

　　輸出若干行，每行為一個整數(shù)，代表某位男士的編號；那位男士必須是一定會擁有伴侶的客人。請按照從小到大的順序輸出他們的編號。

Sample Input

2 3
1 1
2 2 3

Sample Output

1

Hint

【數(shù)據(jù)范圍】
　　對20%的數(shù)據(jù)，有N,M<=10；
　　對40%的數(shù)據(jù)，有N,M<=100；
　　對100%的數(shù)據(jù)，有N,M<=1000。

Solution

• 一開始，我的想法是對于每個人都完整做一遍匈牙利，看看不選他是否會導(dǎo)致不能完全匹配。

• 但這樣明顯會超時。

• 之后我又發(fā)現(xiàn)，其實不需要匹配那么多次。

• 首先先做一次匈牙利，處理出匹配數(shù)組 f ，f[i] 表示第 i 位男士匹配了第 f[i] 為女士。

• 之后枚舉每一位男士 i， 將第 f[i] 位女士重新匹配（不能匹配男士 i），

• 如果還能匹配上就說明男士 i 不是必需的，如果不能匹配了就是必須的。

• 這樣就能通過本題了。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1001; int sum,num,now; bool pd; int a[N][N],f[N],g[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } bool find(int x) {if(g[x]==sum) return false;g[x]=sum;for(int i=1;i<=a[x][0];i++){int y=a[x][i];if(y==now) continue;if(!f[y] || find(f[y])){if(!pd) f[y]=x;return true;}}return false; } int main() {int n=read(),m=read();for(int i=1;i<=n;i++){a[i][0]=read();for(int j=1;j<=a[i][0];j++) a[i][j]=read();}for(int i=1;i<=n;i++) sum++,find(i);for(int i=pd=1;i<=m;i++)if(f[i]){sum++,num=f[now=i],f[i]=0;if(!find(num)) printf("%d\n",i);f[i]=num;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 2308. 【中山市选2011】聚会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。