Codeforces #170 Div1 E. Binary Tree on Plane

この回はC,DよりEの方が正答者が多い。
http://codeforces.com/contest/277/problem/E

問題

2次元座標上でN個の異なる格子点が与えられる。
これらの間をN-1本の辺で接続し、二分木を構築したい。
ただし、辺の両端の２頂点は、Y座標が高い方が親、低い方が子でなければならない。

総辺長を最小化し、その値を答えよ。

解法

うまく辺の長さをコストとしたフローを作り、最小コストフローを求めればよい。
以下のようなフローを考えると良い。

• 各格子点に対応して、フロー上2つの頂点を作る。片方を仮に入力点、もう片方を出力点とする。
• sourceから各出力点にはコスト０容量２の辺を引く。
• 各入力点からsinkにはコスト０容量１の辺を引く。
• 各出力点から、Y座標の小さな格子点の入力店にはコストが格子点間のユークリッド距離、容量１となる辺を引く。

ここでN-1のフローを流せばよい。

なぜ上記のフローで良いかを考えると以下のようになる。
まず、二分木は「根以外の各頂点は親を持つ」「各頂点は2個以下の子を持つ」の条件を考えれば成立する。別に全頂点を連結しないと…などと考える必要はない。

今回入力点からsinkに容量１の辺を引いたが、これは根を除く各頂点が親を1つもつ、言い換えれば各頂点は親からの辺を1つだけ受け入れることを意味する。
逆にsourceから各出力点への容量２の辺は、各頂点は2つまで子を持てることを意味する。

この状況では、1個二分木に辺を加えることは、source→親格子点の出力点→子格子点の入力点→sinkの間に1フローを流すことを意味する。
木の中をずっとフローが流れるのではなく、1辺分だけ流れるのがポイント。
ただし結果的に(N-1)のフローを流すので、(N-1)本の辺ができ、木ができる。

int N;
pair<int,int> P[401];

template<class V_> class MinCostFlow {
public:
	struct edge { int to, capacity; V_ cost; int reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	V_ dist[MV],mav;
	int prev_v[MV], prev_e[MV], NV;
	
	MinCostFlow() { init(MV); mav=1e9;}
	void init(int NV=MV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, V_ cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V_ mincost(int from, int to, int flow) {
		V_ res=0;
		int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, mav);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==mav) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost+1e-9) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			if(dist[to]==mav) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].second>>P[i].first;
	sort(P,P+N);
	if(P[N-1].first==P[N-2].first) return _P("-1\n");
	
	MinCostFlow<double> mcf;
	FOR(i,N) {
		mcf.add_edge(0,10+i*2,2,0);
		mcf.add_edge(10+i*2+1,1,1,0);
	}
	FOR(x,N) FOR(y,N) if(P[x].first>P[y].first) {
		double d=(P[y].second-P[x].second)*(P[y].second-P[x].second)+(P[y].first-P[x].first)*(P[y].first-P[x].first);
		mcf.add_edge(10+x*2,10+y*2+1,1,sqrt(d));
	}
	_P("%.9lf\n",mcf.mincost(0,1,N-1));
}

まとめ

この木の作り方は勉強になった。