PKU演習問メモ(5/1)

あ、あれ四月終わったの……?

No. Title 分類・解法 主観的難易度
2771 Guardian of Decency 二部グラフの最大マッチング ★★★☆☆

以下解説

2771 Guardian of Decency

問題概要

ある授業について、受講者にカップルができないようにしつつ、受講者を最大にしたい。
カップルが出来ないためには、任意の二人の受講者間に以下のいずれかが成り立つ必要がある。

  • 身長差が40cm以上
  • 性別が同じ
  • 音楽の好みが異なる
  • 好きなスポーツが同じ(好きなスポーツが同じだと応援するチームをめぐって喧嘩しやすいため)

各生徒の身長、性別、音楽の好み、好きなスポーツが与えられた時、可能な最大の受講者数を求めよ。

解法

各生徒は男か女であり、同性のカップルはできないことになっているのでこれは二部グラフである。二部グラフの最大独立集合(どの二つの頂点にも辺が引かれていないような部分グラフ)を求めるには、最大マッチングを求めて、頂点の総数からマッチングを引くのが定石。


上の条件のいずれかが成り立つ場合は辺がないとしてグラフをかき、二部グラフのマッチングを求める。


何だか知らないけど制限時間ギリギリだった……

ソースコード
int n;
bool e[500][500];
int p[500];
bool V[500];

bool match(int s)
{
	if(s<0)return 1;
	rep(i,n)if(s!=i&&!V[i]&&e[s][i])
	{
		V[i]=1;
		if(match(p[i]))return p[s]=i,p[i]=s,1;
	}
	return 0;
}

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>n;
		int h[500]; char sex[500]; string music[500],sport[500];
		rep(i,n)
		{
			fill_n(e[i],n,1);
			cin>>h[i]>>sex[i]>>music[i]>>sport[i];
		}
		rep(i,n)rep(j,i)
		{
			if(abs(h[i]-h[j])>40||sex[i]==sex[j]||music[i]!=music[j]||sport[i]==sport[j])
			e[i][j]=e[j][i]=0;
		}
		int ans=n;
		fill_n(p,n,-1);
		rep(i,n)if(sex[i]=='M')
		{
			fill_n(V,n,0);
			if(match(i))ans--;
		}
		cout<<ans<<endl;
	}
	return 0;
}