Beyond the Void
BYVoid
pku 1469 courses
本文正體字版由OpenCC轉換

首先建立二分圖,把P門課程作爲X集合,N個人作爲Y集合,對二分圖進行完備匹配判定。方法是用匈牙利算法求出最大匹配,判斷最大匹配數是否爲P即可。

/* 
 * Problem: pku1469 courses
 * Author: Guo Jiabao
 * Time: 2009.3.25 21:45
 * State: Solved
 * Memo: 求完備匹配
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXP=101,MAXN=301;
using namespace std;
struct edge
{
	edge *next;
	int t;
};
edge *V[MAXP];
edge ES[MAXN*MAXP];
int N,P,EC,Match[MAXN],mat;
bool vis[MAXN];
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a];
	(V[a]=&ES[EC])->t=b;
}
void init()
{
	int i,j,C,a;
	scanf("%d%d",&P,&N);
	EC=-1;
	for (i=1;i<=P;i++)
	{
		scanf("%d",&C);
		V[i]=0;
		for (j=1;j<=C;j++)
		{
			scanf("%d",&a);
			addedge(i,a);
		}
	}
	memset(Match,0,sizeof(Match));
	mat=0;
}
bool path(int i)
{
	for (edge *k=V[i];k;k=k->next)
	{
		int j=k->t;
		if (!vis[j])
		{
			vis[j]=true;
			if (Match[j]==0 || path(Match[j]))
			{
				Match[j]=i;
				return true;
			}
		}
	}
	return false;
}
void hungary()
{
	for (int i=1;i<=P;i++)
	{
		memset(vis,0,sizeof(vis));
		if (path(i))
			mat++;
	}
	if (mat==P)
		printf("YESn");
	else
		printf("NOn");
}
int main()
{
	int i,T;
	freopen("courses.in","r",stdin);
	freopen("courses.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		hungary();
	}
	return 0;
}

上次修改時間 2017-02-03

相關日誌