TopCoder SRM 617 Div1 Medium PieOrDolphin

貪欲でやって本番失敗した問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12738

問題

50人の従業員がいて、N日に２人ずつプレゼントが与えられ、一人はイルカのおもちゃ、もう一人はパイのおもちゃが貰える。

各日でプレゼントがもらえる２名は判明しているが、どちらがどちらを貰うかは決まっていない。
最終的に、各人が貰うイルカとパイの差の絶対値の総和を最少化したい。
そのようなプレゼントの与え方を答えよ。

解法

i日目にプレゼントが貰える２名をX[i]・Y[i]とする。
この問題は従業員を頂点として、X[i]とY[i]を結ぶ辺の向きを決定し、最終的に各頂点の入次数と出次数の差を最少化する問題となる。

よって、もともと次数が奇数の点はどうやっても入次数と出次数の差が１個出てしまうので、とりあえずそのような点から行けるところまで最長パスを適当につなげる。
あとは次数が偶数の点だけになるので適当にDFSして閉路を作ればよい。

class PieOrDolphin {
	public:
	int N;
	vector<int> V;
	int edge[51];
	queue<int> E[51];
	vector<int> C1,C2;
	
	void dfs(int cur) {
		int i;
		while(!E[cur].empty()) {
			int e=E[cur].front();
			E[cur].pop();
			
			if(V[abs(e)-1]) continue;
			
			edge[cur]--;
			if(e<0) {
				V[-e-1]=1;
				edge[C1[-e-1]]--;
				dfs(C1[-e-1]);
			}
			else {
				V[e-1]=2;
				edge[C2[e-1]]--;
				dfs(C2[e-1]);
			}
			return;
		}
	}
	
	vector <int> Distribute(vector <int> choice1, vector <int> choice2) {
		C1=choice1;
		C2=choice2;
		
		N=choice1.size();
		int i,x,y,j;
		
		ZERO(edge);
		FOR(x,50) E[x]=queue<int>();
		
		V=vector<int>(N,0);
		
		FOR(i,N) {
			E[C1[i]].push(i+1);
			E[C2[i]].push(-(i+1));
			edge[C1[i]]++;
			edge[C2[i]]++;
		}
		
		FOR(i,50) if(edge[i]%2) dfs(i);
		FOR(i,50) if(edge[i]) dfs(i);
		
		return V;
	}
}

まとめ

本番「閉路をうまく作らないと…」とか考えてしまったけど、適当に作っても良かったのね…。