TopCoder Open 2012 Round 2A Div1 Easy SwitchesAndLamps

問題

n個のランプとn個のスイッチがあり、
それぞれのランプはそれぞれ異なるスイッチただ一つにつながっている。

スイッチがOFFのとき、対応するランプもOFFである。
いま、スイッチをswitch[i]で表されるスイッチをONにしたところ、
それぞれlump[i]で表されるランプがONになった。

後何回かこの試行を繰り返し、
全てのランプとスイッチを対応づけたい。
必要な試行回数の最小値を求めよ。

与えられた試行が矛盾している場合は-1を返せ。

制約条件

n, m≦50

方針

以下ちゃんとしてない説明。

スイッチとランプを頂点とするような二部グラフで対応関係を考える。
最初は、全てのスイッチと全てのランプが対応する可能性があるので、全てのスイッチとランプ間に枝がある。
試行一回で何が起こるかというと、

ONのスイッチの集合とOFFのランプの集合が分離し、
OFFのスイッチの集合とONのランプの集合が分離する。
これは、スイッチとランプの連結成分が二つに分かれることを意味していて、
しかもそれぞれ分かれた二つのグラフはまた二部完全グラフになっている。

なので、後何回試行が必要かは、それぞれの集合のサイズのみに依存する。
一回の実験でサイズが半分になるように集合を分解していくのが最善。

それぞれの連結成分について、サイズ≦2^kとなるような最小のkを求めて
それのmaxを取れば答えが求まる。

ソースコード

本番で送った奴

int n, p[100], v[100];
bool can[100][100];

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

class SwitchesAndLamps {
	public:
	int theMin(vector <string> switches, vector <string> lamps) 
	{
		n = lamps[0].size();
		memset(can, 0, sizeof(can));
		rep(i,n) rep(j,n) can[i][j + n] = can[j + n][i] = 1;
		
		rep(i,lamps.size()){
			rep(j,n) rep(k,n) if(switches[i][j] != lamps[i][k])
				can[j][k + n] = can[k + n][j] = 0;
		}
		
		rep(i,2*n){
			int cnt = 0;
			rep(j,2*n) if(can[i][j]) cnt++;
			if(cnt == 0) return -1;
			cnt = 0;
			rep(j,2*n) if(can[j][i]) cnt++;
			if(cnt == 0) return -1;
		}
		
		int used = 0;
		
		while(1){
			bool update = 0;
			
			rep(i,2*n){
				int cnt = 0, p;
				rep(j,2*n) if(can[i][j]) cnt++, p = j;
				if(cnt == 1){
					used++; update = 1;
					rep(j,2*n) can[i][j] = can[j][i] = can[j][p] = can[p][j] = 0;
				}
				rep(j,2*n) if(can[j][i]) cnt++, p = j;
				if(cnt == 1){
					used++; update = 1;
					rep(j,2*n) can[j][i] = can[i][j] = can[p][j] = can[j][p] = 0;
				}
			}
			if(!update) break;
		}
		used /= 2;
		//rep(i,2*n) rep(j,2*n) cerr<<can[i][j]<<(j==2*n-1?"\n":" ");
		rep(i,2*n) p[i] = -1;
		rep(i,2*n) if(p[i] < 0){
			rep(j,2*n) v[j] = 0;
			if(match(i)) used++;
		}
		//dbg(used);
		if(used != n) return -1;
		
		rep(k,2*n) rep(i,2*n) rep(j,2*n) can[i][j] |= can[i][k] && can[k][j];
		rep(i,2*n) v[i] = 0;
		int ans = 0;
		rep(i,2*n) if(!v[i]){
			int sz = 1, deg = 0;
			rep(j,2*n) if(can[i][j]) deg++;
			if(deg == 0) continue;
			v[i] = 1;
			rep(j,2*n) if(!v[j] && (can[i][j] || can[j][i])){
				v[j] = 1;
				int deg = 0;
				rep(k,2*n) if(can[j][k]) deg++;
				if(deg)sz++;
			}
			sz /= 2;
			int cnt = 0, p = 1;
			while(p < sz) p *= 2, cnt++;
			ans = max(ans, cnt);
		}
		return ans;
	}
};