//題目類型：二分圖的最大匹配
//基礎的二分匹配題：使用匈牙利算法實現，可以作為模板
//注：使用scanf,prinf輸入輸出否則會超時
#include <stdio.h>
#include <string.h>
//#include <conio.h>
#define arraysize 201
int map[arraysize][arraysize];
int match[arraysize];
bool final[arraysize];
int n,m;
bool DFS(int p)
{
???? int i,j;
???? int temp;
???? for(i=1;i<m+1;++i)
???? {
??????? if(map[p][i] && !final[i])
??????? {
??????????? final[i] = true;
??????????? temp = match[i];
??????????? match[i] = p;
??????????? if(temp==0 || DFS(temp)) return true;
??????????? match[i] = temp;
??????? }
???? }
???? return false;
}
int mat()
{
??? int i,j;
??? int maxmatch = 0;
??? for(i=1;i<n+1;++i)
??? {
??????? memset(final,0,sizeof(final));
??????? if(DFS(i)) maxmatch++;????
??? }
??? return maxmatch;
}
int main()
{
??? //freopen("1.txt","r",stdin);
??? int i,j;
??? while(scanf("%d%d",&n,&m)!=EOF)
??? {
?????? memset(map,0,sizeof(map));
?????? memset(match,0,sizeof(match));
?????? for(i=1;i<n+1;++i)
?????? {
?????????? int tempcount;
?????????? //cin>>tempcount;
?????????? scanf("%d",&tempcount);
?????????? int milk;
?????????? for(j=0;j<tempcount;++j)
?????????? {
?????????????? //cin>>milk;
?????????????? scanf("%d",&milk);
?????????????? map[i][milk] = 1;
?????????? }
?????? }
?????? //cout<<mat()<<endl;
?????? printf("%d\n",mat());
??? }
??? //getch();
??? return 0;
}

轉載于:https://www.cnblogs.com/north_dragon/archive/2010/05/06/1729291.html

總結

以上是生活随笔為你收集整理的POJ 1274题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。