TopCoder SRM 653 Div1 Medium Singing

450ptなのにうまくグラフ作れず解けなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=13680

問題

1～NのN通りの高さの音符で構成される歌があり、i番目の音符の音の高さはP[i]である。
Aliceは音の高さがlow～Nの範囲の音符を歌え、Bobは1～highの範囲の音符を歌える。

AliceとBobで音符を分担し、Pで表される歌を歌いたい。
その際、同じ高さの音符はAliceとBobのどちらかがすべて担当しなければならない。
Pを歌う際、最適に音符の担当を定めた場合、AliceとBobの担当の切り替え回数の最小値を求めよ。

解法

最小カットを求める問題に変換することで、最大フローを用いて解くことができる。
いわゆる埋める燃やす問題に近い。

高さが1～(low-1)の範囲は必ずBobが歌い、(high+1)～Nの範囲は必ずAliceが歌う。
後はlow～highの範囲をどう2人に分担させるかということになる。

これには以下のように有効グラフを作成すればよい。

• まずsource・sinkと1～Nの音符に対応する頂点の計(N+2)頂点を作る。
• 次にsourceから1～(low-1)、すなわちBobが歌うの確定の頂点に容量無限大の有向辺を張る。
• 同様に(high+1)～N、すなわちAliceが歌うの確定の頂点からsinkに容量無限大の有向辺を張る。
• P[i]!=P[i+1]、すなわち歌で隣接する音符の高さが異なるとき、P[i]とP[i+1]の間に双方向に容量1の辺を張る。
  • もしP[i]とP[i+1]の担当がAliceとBobに分かれると、そこにフロー1が流れることになり、これは担当切り替え回数が1個増えることに相当する。
  • P[i]とP[i+1]の担当が同じならフローは流れない。

上記グラフでsourceからsinkへの最小カットが、すなわち最小切り替え回数となる。
あとは最大フローを求めればよい。

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 2200;
	vector<edge> E[MV];
	int itr[MV],lev[MV];
	
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	
	void bfs(int cur) {
		MINUS(lev);
		queue<int> q;
		lev[cur]=0;
		q.push(cur);
		while(q.size()) {
			int v=q.front(); q.pop();
			ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to);
		}
	}
	
	V dfs(int from,int to,V cf) {
		if(from==to) return cf;
		for(;itr[from]<E[from].size();itr[from]++) {
			edge* e=&E[from][itr[from]];
			if(e->cap>0 && lev[from]<lev[e->to]) {
				V f=dfs(e->to,to,min(cf,e->cap));
				if(f>0) {
					e->cap-=f;
					E[e->to][e->reve].cap += f;
					return f;
				}
			}
		}
		return 0;
	}
	
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			bfs(from);
			if(lev[to]<0) return fl;
			ZERO(itr);
			while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf;
		}
	}
};


class Singing {
	public:
	int solve(int N, int low, int high, vector <int> pitch) {
		int i;
		MaxFlow_dinic<int> mf;
		for(i=1;i<=low-1;i++) mf.add_edge(0,i,pitch.size()-1);
		for(i=high+1;i<=N;i++) mf.add_edge(i,N+1,pitch.size()-1);
		FOR(i,pitch.size()-1) if(pitch[i]!=pitch[i+1]) mf.add_edge(pitch[i],pitch[i+1],1,true);
		return mf.maxflow(0,N+1);
	}
}

まとめ

本番最小カットになることは思いついたが、このグラフは重い浮かばなかった。
1～Nに対応する頂点を2セット考えてしまい、うまいグラフが出来ず苦悶してしまった。