CJOJ 1943 【重庆八中模拟赛】寻找代表元（二分图最大匹配）
Description
八中一共有n个社团，分别用1到n编号。 八中一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。 每个社团都需要选一个代表。我们希望更多的人能够成为代表。这里，每个人至多代表一个社团且每个社团至多有一个代表。
第一行输入两个数n和m。 以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。
Output
输出最多的能够成为代表的人数。
4 4 1 2 0 1 2 0 1 2 0 1 2 3 4 0
Sample Output
3
Http
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1943
Source
二分图的最大匹配
解决思路
二分图最大匹配，不多说，参考我之前的这几篇文章：http://www.cnblogs.com/SYCstudio/p/7138206.htmlhttp://www.cnblogs.com/SYCstudio/p/7138221.htmlhttp://www.cnblogs.com/SYCstudio/p/7138230.html
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxN=300;
const int inf=2147483647;
int n,m;
vector<int> E[maxN];
int Match[maxN];
bool vis[maxN];
bool Hungary(int u);
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
int x;
while (cin>>x)
{
if (x==0)
break;
E[i].push_back(x);
}
}
int Ans=0;
memset(Match,-1,sizeof(Match));
for (int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if (Hungary(i))
Ans++;
}
cout<<Ans<<endl;
return 0;
}
bool Hungary(int u)
{
for (int i=0;i<E[u].size();i++)
{
int v=E[u][i];
if (vis[v]==0)
{
vis[v]=1;
if ((Match[v]==-1)||(Hungary(Match[v])))
{
Match[v]=u;
return 1;
}
}
}
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7138237.html
