AOJ 2293 - Dangerous Tower

最小費用流の勉強になった

問題

n個の積み木があり、i番目は1*a[i]*b[i]の直方体の形をしている
これらを積み重ねてなるべく高い塔を作りたい
長さ1の辺を奥行き方向に用いて、他の2辺を横方向と縦方向に1つずつ割り当てる(どっちをどっちにしてもok)
積み上げるとき、上の段の積み木は下の段の積み木より横の長さが厳密に短くなければいけない
作れる塔の高さの最大値を求めよ

1 <= n <= 10^3
1 <= a[i], b[i] <= 10^6

解法

最小費用流に落とし込んで解く

横の長さが異なるように積み木を選べばそれらは全て使える
つまり順番は考えなくてよく、一度横の長さとして使った長さは二度と使えないという条件に言い換えられる
また、塔の高さを点数とすると、「積み木iを使う場合、横の長さをa[i]にするとb[i]点、逆ならa[i]点得られる」と言える
これらをうまく最小費用流で表現するには・・↓

aとbという2n個の値から重複を取り除き、それぞれに1から始まる番号を付ける(座標圧縮)
便宜上これらをまとめてXと呼び、n個の積み木たちはYと呼ぶ
で、↓のように有向辺を張る
・始点からXの各値(各頂点)に容量1コスト0の辺を張る
・Yの各頂点iに向かって、「Xのa[i]に対応する頂点」から容量1コスト-b[i]の辺、「Xのb[i]に対応する頂点」から容量1コスト-a[i]の辺を張る
・Yの各頂点から終点に容量1コスト0の辺を張る
・始点から終点に容量無限コスト0の辺を張る
最後の辺の流量は使わない積み木の個数に対応する
見づらいけどサンプル1は↓のようになる

このグラフで最小費用流を求めて-1をかければそれが答え

実装

各値には1からid-1までの番号が付く
始点: 0
Xの各頂点: 1〜id-1
Yの各頂点: id〜n-1
終点: id+n
という対応

const int MAXV = 4040;
class MCF {
private:
	struct edge {int to, cap, cost, rev;};
	vector<edge> g[MAXV];
	int V, h[MAXV], dist[MAXV], prevv[MAXV], preve[MAXV];
public:
	// fromからtoへ向かう容量capコストcostの辺をグラフに追加する
	void add_edge(int from, int to, int cap, int cost) {
		g[from].push_back((edge){to, cap, cost, (int)g[to].size()});
		g[to].push_back((edge){from, 0, -cost, (int)g[from].size()-1});
	}
	// sからtへの流量fの最小費用流を求める (流せない場合は-1)
	int getflow(int s, int t, int f, int n) {
		V = n;
		int res = 0;
		fill(h, h+V, 0);
		if (0<f) {
			fill(h, h+V, 1<<30);
			h[s] = 0;
			while (1) {
				bool upd = 0;
				for (int i=0; i<V; i++) for (auto &e : g[i]) if (e.cap) {
					if (h[i]==(1<<30)) continue;
					if (h[e.to] > h[i]+e.cost) {
						h[e.to] = h[i] + e.cost;
						upd = 1;
					}
				}
				if (!upd) break;
			}
		}
		while (0<f) {
			priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
			fill(dist, dist+V, 1<<30);
			dist[s] = 0;
			que.push({0,s});
			while (!que.empty()) {
				pair<int,int> p = que.top(); que.pop();
				int v = p.second;
				if (dist[v]<p.first) continue;
				for (int i=0; i<g[v].size(); i++) {
					edge &e = g[v][i];
					if (0<e.cap && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v, preve[e.to] = i;
						que.push({dist[e.to], e.to});
					}
				}
			}
			if (dist[t]==(1<<30)) return -1;
			for (int v=0; v<V; v++) h[v] += dist[v];
			int d = f;
			for (int v=t; v!=s; v=prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
			f -= d;
			res += d*h[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;
			}
		}
		return res;
	}
};

int n, a[1010], b[1010], id = 1;
map<int,int> m;
MCF mcf;

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i] >> b[i];
		if (!m[a[i]]) m[a[i]] = id++;
		if (!m[b[i]]) m[b[i]] = id++;
	}
	reps(i,1,id) mcf.add_edge(0,i,1,0);
	rep(i,n) {
		mcf.add_edge(m[a[i]],id+i,1,-b[i]);
		mcf.add_edge(m[b[i]],id+i,1,-a[i]);
		mcf.add_edge(id+i,id+n,1,0);
	}
	mcf.add_edge(0,id+n,n,0);
	cout << -mcf.getflow(0,id+n,n,id+n+1) << endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2293&lang=jp