3692 Kindergarten
問題概要
幼稚園にはB人の男の子およびG人の女の子がいる。
男の子同士、女の子同士は全てお互いに知り合いである。
また、M組、お互いに知り合いの男女のペアがある。
この中から任意二人が知り合いであるようなグループを作るとき、そのようなグループの最大の人数を求めよ。
G,B≦200を満たす。
解法
知り合いの関係を辺で表わした無向グラフを考えると、求めるものはグラフの最大クリーク(任意の二頂点間に辺があるような部分集合)である。
一般にグラフにおいて最大クリーク=補グラフの最大独立集合が成り立つため、
補グラフを考えてみる。補グラフとは、辺のあった頂点間には辺がなく、辺のない頂点間には辺を張るようなグラフのことである。
この補グラフは、男の子と女の子の頂点にしか辺がないため二部グラフになっている。
したがって、最大独立集合を求めるには、最大マッチングを求めて、頂点の数から引けばよい。
ソースコード
int b,g,m,n,p[400],C; bool e[400][400],v[400]; bool match(int s){ if(s<0)return 1; rep(i,n)if(e[s][i]&&!v[i]){ v[i]=1; if(match(p[i]))return p[i]=s,p[s]=i,1; } return 0; } int main(){ while(scanf("%d%d%d",&b,&g,&m),b){ n=b+g; rep(i,n)rep(j,n)e[i][j]=0; rep(i,b)rep(j,g)e[i][j+b]=1; rep(i,m){ int s,t; scanf("%d%d",&s,&t); s--; t--; e[s][t+b]=e[t+b][s]=0; } int ans=n; rep(i,n)p[i]=-1; rep(i,b){ rep(j,n)v[j]=0; if(match(i))ans--; } printf("Case %d: %d\n",++C,ans); } return 0; }