站酷做网站/我要看今日头条

主题链接：

http://poj.org/problem?

id=1274

题目大意：

有N头奶牛(编号1~N)和M个牛棚(编号1~M)。

每头牛仅仅可产一次奶。每一个牛棚也仅仅同意一仅仅牛产奶。

如今给出每头奶牛喜欢去的牛棚的编号。问：最多有多少头奶牛能完毕产奶。

思路：

二分图最大匹配问题，建立一个图，用行来表示奶牛，用列来表示牛棚。将奶牛和喜欢去的牛棚编号

连边。

然后用匈牙利算法DFS版或BFS版求二分图的最大匹配数就可以。这里用了匈牙利算法DFS版。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;const int MAXN = 220;bool Map[MAXN][MAXN];
bool bMask[MAXN];int NX,NY;
int cx[MAXN],cy[MAXN];int FindPath(int u)
{for(int i = 1; i <= NY; ++i){if(Map[u][i] && !bMask[i]){bMask[i] = 1;if(cy[i] == -1 || FindPath(cy[i])){cy[i] = u;cx[u] = i;return 1;}}}return 0;
}int MaxMatch()
{int res = 0;for(int i = 1; i <= NX; ++i)cx[i] = -1;for(int i = 1; i <= NY; ++i)cy[i] = -1;for(int i = 1; i <= NX; ++i){if(cx[i] == -1){for(int j = 1; j <= NY; ++j)bMask[j] = 0;res += FindPath(i);}}return res;
}int main()
{int d,id;while(~scanf("%d%d",&NX,&NY)){memset(Map,0,sizeof(Map));for(int i = 1; i <= NX; ++i){scanf("%d",&id);for(int j = 1; j <= id; ++j){scanf("%d",&d);Map[i][d] = 1;}}printf("%d\n",MaxMatch());}return 0;
}