Codeforces 277E (170E) Binary Tree on Plane

問題

座標平面上にn個の点がある。
このn個の点を以下の条件を満たす辺でつなぎたい。

  • 辺はy[i] > y[j]であるときに限りiからjに張ることができる
  • 全ての点は連結である
  • 全ての点の入次数は1以下、出次数は2以下
  • 辺の長さの和が最小になる

このとき、辺の長さの和の最小値を求めよ。

制約条件

n≦400

方針

各頂点をINとOUTに分割する。
出次数は2以下なので、sからOUTに容量2、コスト0の辺を張る。
入次数は1以下なので、INからtに容量1、コスト0の辺を張る。
y[i] > y[j]なる頂点iのOUTからjのINに、容量1、コスト距離の辺を張る。


このグラフで流量n-1の最小費用流を求めればよい。

ソースコード

int n, x[400], y[400];

int main(){
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	
	int s = 2 * n, t = 2 * n + 1;
	costflowGraph<double> g(2 * n + 2);
	
	rep(i, n){
		g.add(s, i + n, 2, 0);
		g.add(i, t, 1, 0);
	}
	rep(i, n) rep(j, n) if(y[i] > y[j]){
		g.add(i + n, j, 1, hypot(x[i] - x[j], y[i] - y[j]));
	}
	printf("%.12f\n", g.min_cost_flow(s, t, n - 1));
	
	return 0;
}