正规的二分图匹配，用匈牙利算法实现。

//a group of N students and P courses
//2201302 2010-03-17 21:29:03 Accepted 1083 500MS 332K 1063 B G++ 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int P = 102;//the number of course
const int N = 304;//the number of students

bool mat[N][P];
int useif[P];
int link[P];
int p, n;

bool dfs(int cc)
{
	int i;
	for(i = 1; i <= p; i++)
	{
		if(!useif[i] && mat[cc][i])
		{
			useif[i] = true;
			if(link[i] == -1 || dfs(link[i]))
			{
				link[i] = cc;
				return true;
			}
		}
	}
	return false;
}

int MaxMatch()
{
	int i , sum = 0;
	memset(link, -1, sizeof(link));
	for(i = 1; i <= n; i++)
	{
		memset(useif, false, sizeof(useif));
			if(dfs(i))
				sum++;
	}
	return sum;
}

int main()
{
	int T;
	int i, tc, cc;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &p, &n);
		memset(mat, false, sizeof(mat));
		for(i = 1; i <= p; i++)
		{
			scanf("%d", &tc);
			while(tc--)
			{
				scanf("%d", &cc);
				mat[cc][i] = true;
			}
		}
		if(MaxMatch() == p)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

• 相关文章
• 全局相关文章