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; }