AOJ 2095 Nagashi Soumen

AOJ 動的計画法 フロー グラフ理論

問題

空間上にn個の点があり、それぞれの座標は(x[i], y[i], z[i])である。
点をk本以下のパイプでつなぐ。


パイプは、

  • 自由にまげて良い。
  • 分岐したり、合流したりしてはいけない。
  • どこを始点、終点としてもよい。
  • 始点または終点または、途中の任意の点で、空間上の点を通ることができる。
  • z座標が真に大きい点から小さい点にしかつなげない。
  • 全ての点が、どれか1本以上のパイプにつながるようにする。

このとき、パイプの全長の最小値はいくつか、求めよ。

制約条件

n≦100
0≦x[i],y[i],z[i]≦100

方針

次のような費用流で解いた。


各点をIN, OUTの二頂点に分割する。
INからOUTに容量1、コスト0の辺を張る。


パイプでつなげる頂点間をa, bとする。
aのOUTからbのINへ、容量1、コストdist(a, b)の辺を張る。


始点から全てのパイプのINへ容量1、コスト0の辺、
終点から全てのパイプのOUTへ容量1、コスト0の辺を張る。


ここに、更に流量制約INからOUTの最小流量1という条件を付け加えたときの、
最小費用最大流が求めるパイプの全長の最小値。


費用流に最小流量の制約があるときは、蟻本にあるように、
適当に下駄をはかせて、必ずその辺が使われるように処理する。


想定解はDPっぽい。

ソースコード

typedef pair<long double, int> P;
struct edge{
	int to, cap, rev;
	long double cost;
	 
	edge(int to, int cap, long double cost, int rev) :
		to(to), cap(cap), cost(cost), rev(rev){
	}
};
 
const int MAX_V = 210;
int V, prevv[MAX_V], preve[MAX_V];
vector<edge> G[MAX_V];
long double h[MAX_V], dist[MAX_V];

void add_edge(int from, int to, int cap, long double cost){
	G[from].pb(edge(to, cap, cost, G[to].size()));
	G[to].pb(edge(from, 0, -cost, G[from].size() - 1));
}
 
long double min_cost_flow(int s, int t, int f){
	long double res = 0;
	while(f > 0){
		fill(dist, dist + V, INF);
		dist[s] = 0;
		int d = f;
		 
		rep(it, V){
			bool update = 0;
			rep(v, V){
				if(dist[v] == INF) continue;
				rep(i, G[v].size()){
					edge &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + EPS){
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						update = 1;
					}
				}
			}
			if(!update) break;
		}
		if(dist[t] == INF) return -INF;
		 
		for(int v = t; v != s; v = prevv[v]){
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * dist[t];
		for(int v = t; v != s; v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
		NEXT:;
	}
	return res;
}
 
inline long double sq(long double x){
	return x * x;
}
 
const double BIG = 1e6;
int n, k, x[100], y[100], z[100];
 
int main(){
	while(cin >> n >> k, n){
		V = 2 * n + 2;
		rep(i, V) G[i].clear();
		rep(i, n) cin >> x[i] >> y[i] >> z[i];
		rep(i, n){
			add_edge(V - 2, i * 2, 1, 0);
			add_edge(i * 2, i * 2 + 1, 1, -BIG);
			add_edge(i * 2 + 1, V - 1, 1, 0);
		}
		rep(i, n) rep(j, n) if(z[i] > z[j]){
			long double dist = sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j]) + sq(z[i] - z[j]));
			add_edge(i * 2 + 1, j * 2, 1, dist);
		}
		k = min(k, n);
		long double ans = min_cost_flow(V - 2, V - 1, k);
		if(ans == -INF){
			cout << -1 << endl;
		}
		else{
			ans += BIG * n;
			if(ans > BIG - EPS || ans < -EPS) cout << -1 << endl;
			else cout << setiosflags(ios::fixed) << setprecision(20) << ans << endl;
		}
		 
	}
	return 0;
}