题目链接:
https://vjudge.net/problem/POJ-1274
题目大意:
有n个奶牛和m个谷仓,现在每个奶牛有自己喜欢去的谷仓,并且它们只会去自己喜欢的谷仓吃东西,问最多有多少奶牛能够吃到东西
输入第一行给出n与m接着n行每行第一个数代表这个奶牛喜欢的谷仓的个数P,后面接着P个数代表这个奶牛喜欢哪个谷仓
思路:
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
int Map[maxn][maxn];
int cx[maxn], cy[maxn];
//cx[i]表示与x部的点i匹配的y部的点的编号
//cy[i]表示与y部的点i匹配的x部的点的编号
bool vis[maxn];//标记y部的点是否加入增广路
int cntx, cnty;//x部点的数目和y部点的数目 bool dfs(int u)//dfs进入的都是x部的点
{
for(int v = ; v <= cnty; v++)//枚举y部的点
{
if(Map[u][v] && !vis[v])//存在边,并且还未加入增广路
{
vis[v] = ;//标记加入增广路
//如果Y部的点v还未被匹配
//或者已经被匹配了,但是可以从v点原来匹配的cy[v]找到一条增广路
//说明这条路就可是一个正确的匹配
if(cy[v] == - || dfs(cy[v]))
{
cx[u] = v;
cy[v] = u;
return true;
}
}
}
return false;//不能匹配
}
int maxmatch()//匈牙利算法找最大匹配
{
int ans = ;
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));//初始化均未匹配
for(int i = ; i <= cntx; i++)//枚举x部的点
{
if(cx[i] == -)//还未匹配,寻找从i点出发是否存在增广路
{
memset(vis, , sizeof(vis));
ans += dfs(i);
}
}
return ans;
}
int main()
{
while(cin >> cntx >> cnty)
{
memset(Map, , sizeof(Map));
int v, t;
for(int u = ; u <= cntx; u++)
{
cin >> t;
while(t--)
{
cin >> v;
Map[u][v] = ;
}
}
cout<<maxmatch()<<endl;
//for(int i = 1; i <= cntx; i++)cout<<i<<" "<<cx[i]<<endl;
}
}