TopCoder SRM 589 Div1 Medium GearsDiv1

さてMedium。あっさり解けていい気になってたら落とした。
http://community.topcoder.com/stat?c=problem_statement&pm=12729

問題

RGB３色の歯車がある。
また、どの歯車とどの歯車が噛んでいるかがグラフで与えられる。
(ただし、同じ色の歯車同士はかみ合わない)

同じ色の歯車は同じ向きに回る。
また、かみ合う歯車同士は逆向きにかみ合わないといけない。
このとき、すべての歯車を回すよう、余計な歯車をいくつか外したい。
外さないといけない最小の歯車数を答えよ。

解法

RGBの歯車の回り方を(左,左,右)(左,右,左)(左,右,右)の３通りすべて試す。
(対称性からRが右のパターンは不要だし、全部左周りより右が混じる方が良いことは確定的なので上記３通りだけでよい)

元々同じ色の歯車はかまないので、例えばRGB=(左,左,右)のケースではRとGの歯車が噛んでしまっていると、どちらかを外さないといけない。

本番、ここまではあっていたが外す歯車の選び方がまずかった…。

Rの歯車群とGの歯車群で２部グラフを作り、最大マッチングを求める。
その数が外すべき歯車の数である(マッチング辺の両端のどちらかを外すことに相当)。

上記処理を３通りの回しかたで試せばよい。
下のコードは二部マッチングじゃなく最大フローでやってるけどね。

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0) {
				if((tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
					e.capacity -= tf;
					E[e.to][e.reve].capacity += tf;
					return tf;
				}
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


class GearsDiv1 {
	public:
	int N;
	int sp[3];
	int C[51];
	vector<string> G;
	int van[51];
	int mi;
	
	int testtest() {
		MaxFlow mf;
		int i,j;
		FOR(i,N) {
			if(sp[C[i]]==0) mf.add_edge(0,100+i,1);
			if(sp[C[i]]==1) mf.add_edge(200+i,300,1);
			FOR(j,N) {
				if(sp[C[i]]==0 && sp[C[j]]==1 && G[i][j]=='Y') mf.add_edge(100+i,200+j,1);
			}
		}
		
		return mf.maxflow(0,300);
	}
	
	
	int getmin(string color, vector <string> graph) {
		N=color.size();
		
		int i;
		G=graph;
		FOR(i,N) {
			if(color[i]=='R') C[i]=0;
			if(color[i]=='G') C[i]=1;
			if(color[i]=='B') C[i]=2;
		}
		
		int mi=100;
		sp[0]=0; sp[1]=1; sp[2]=2; mi=min(mi,testtest());
		sp[0]=0; sp[1]=2; sp[2]=1; mi=min(mi,testtest());
		sp[0]=2; sp[1]=0; sp[2]=1; mi=min(mi,testtest());
		return mi;
	}
};

まとめ

最初の回答があっさり通ったため本番はそれで出してしまった。
その後練習ではどう二部グラフに落とせばよいかわからず手間取った。