TopCoder SRM 617 Div1 Medium PieOrDolphin

問題

50人の人がいて、n日間二人ずつプレゼントが渡される。
i日目にプレゼントを渡される人はchoice1[i]およびchoice2[i]である。
プレゼントはPieまたはDolphinで、どちらが渡されるかは決まってない。

全てのプレゼントを渡し終えた後、
各人が持っている|Pieの個数 - Dolphinの個数|の和が最小になるようにプレゼントを配りたい。
プレゼントの配り方をどれか一通り出力せよ。

制約条件

n≦1000
choice1[i], choice2[i]≦50
choice1[i]≠choice2[i]

方針

それぞれの人を頂点として、(choice1[i], choice2[i])に辺があるようなグラフを考える。
Pieを得ることを+1, Dolphinを得ることを-1として、それぞれの人の得点の絶対値の和を最小化する問題としてよい。

渡すプレゼントを選ぶのは、辺のどちら側の頂点に1を足して、どちら側の頂点から1を引くかという操作に置き換えられるので、辺の向き付けを考えることになる。
向き付けをおこなった後、ループができると、そこでの失点がゼロになる。

なのでなるべくループを作りたい。
ループはどのような順番で作っても出来る数は一緒（次数を２ずつ消費する）なので、
貪欲というか取れる順に適当に取っていってしまってかまわない。

森が残るが、パス１本につき失点が２増えるので、
なるべく少ないパスで森の辺を被覆したい。
これは次数が１の頂点から適当にパスを取っていけば達成される。

ソースコード

class PieOrDolphin {
	public:
	
	int n;
	vi ans, c1, c2;
	map<pi, int> id;
	
	vector <int> Distribute(vector <int> choice1, vector <int> choice2) {
		c1 = choice1;
		c2 = choice2;
		n = c1.size();
		id.clear();
		ans.clear();
		ans.resize(n);
		
		rep(i, n){
			int a = choice1[i], b = choice2[i];
			if(a > b) swap(a, b);
			
			if(id.count(mp(a, b))){
				int prev = id[mp(a, b)];
				
				fix(prev, a, b);
				fix(i, b, a);
				id.erase(mp(a, b));
			}
			else id[mp(a, b)] = i;
		}
		
		//remove loop
		vector<vi> e(50);
		{
			int st[100], sz;
			bool v[100];
			
			each(i, id){
				int a = i->first.first, b = i->first.second;
				e[a].pb(b);
				e[b].pb(a);
			}
			while(1){
				memset(v, 0, sizeof(v));
				bool fin = 1;
				
				rep(i, 50) if(!v[i]){
					sz = 0;
					if(!check_loop(i, i, e, st, sz, v)) continue;
					
					rep(j, sz){
						int a = st[j], b = st[(j + 1) % sz];
						int eid = id[mp(min(a, b), max(a, b))];
						
						fix(eid, a, b);
						erase(e, a, b); erase(e, b, a);
					}
					fin = 0;
					break;
				}
				if(fin) break;
			}
		}
		#if 0
		rep(i, 50) if(e[i].size()){
			cerr<<"i: "<<i<<" sz: "<<e[i].size()<<endl;
		}
		#endif
		
		//pick a tree and solve it
		while(1){
			bool fin = 1;
			rep(i, 50) if(e[i].size() == 1){
				
				int st[100];
				int sz = 0;
				int c = i, p = i;
				
				while(1){
					st[sz++] = c;
					int next = -1;
					
					rep(j, e[c].size()) if(e[c][j] != p){
						
						next = e[c][j];
						break;
					}
					if(next < 0) break;
					
					p = c;
					c = next;
				}
				//rep(j, sz) cerr<<st[j]<<" ";cerr<<endl;
				
				rep(j, sz - 1){
					int a = st[j], b = st[j + 1];
					int eid = id[mp(min(a, b), max(a, b))];
					
					fix(eid, a, b);
					erase(e, a, b); erase(e, b, a);
				}
				fin = 0;
				break;
			}
			if(fin) break;
		}
		
		return ans;
		
	}
	bool check_loop(int c, int p, const vector<vi> &e, int *st, int &sz, bool *v){
		
		st[sz++] = c;
		v[c] = 1;
		
		rep(i, e[c].size()) if(e[c][i] != p){
			
			if(v[e[c][i]]){
				
				int pos;
				for(pos = 0; pos < sz && st[pos] != e[c][i]; pos++);
				for(int j = pos; j < sz; j++) st[j - pos] = st[j];
				sz -= pos;
				
				return 1;
			}
			
			if(check_loop(e[c][i], c, e, st, sz, v)) return 1;
		}
		sz--;
		return 0;
	}
	void erase(vector<vi> &e, int a, int b){
		
		for(int i = (int)e[a].size() - 1; i >= 0; i--) if(e[a][i] == b)
			e[a].erase(e[a].begin() + i);
	}
	void fix(int idx, int a, int b){
		
		if(c1[idx] == a) ans[idx] = 1;
		else ans[idx] = 2;
	}
};