题目链接:
?pid=1179
题目大意:
题目太长了,,简单的意思就是:有N个魔杖,M个魔法师,魔杖有多个匹配的魔法师。但是一个魔法师
只能对应一根魔杖。那么问题来了:最多有多少魔法师能得到魔棒。
思路:
做一个二分图,一边是魔杖,另一边是魔法师。相应的匹配作为二分图的边。利用匈牙利算法,求出二
分图最大匹配是多少。
AC代码:
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 110;bool Map[MAXN][MAXN],mask[MAXN];int N,M,cx[MAXN],cy[MAXN];int FindPath(int u){for(int i = 1; i <= M; ++i){if(Map[u][i] && !mask[i]){mask[i] = 1;if(cy[i] == -1 || FindPath(cy[i])){cy[i] = u;cx[u] = i;return 1;}}}return 0;}int MaxMatch(){int ret = 0;for(int i = 1; i <= N; ++i)cx[i] = -1;for(int i = 1; i <= M; ++i)cy[i] = -1;for(int i = 1; i <= N; ++i){if(cx[i] == -1){for(int j = 1; j <= M; ++j)mask[j] = 0;ret += FindPath(i);}}return ret;}int main(){int d,w;while(~scanf("%d%d",&N,&M)){memset(Map,false,sizeof(Map));for(int i = 1; i <= M; ++i){scanf("%d",&d);while(d–){scanf("%d",&w);Map[w][i] = 1;}}printf("%d\n",MaxMatch());}return 0;}
孝敬父母、疼爱孩子、体贴爱人、善待朋友。