POJ 3068: "Shortest" pair of paths

http://poj.org/problem?id=3068

POJ 2135(蟻本p214)とほぼ一緒。
ただ今度は点も共有してはいけないので点の数を二倍にして、点の間に容量1、コスト0の辺を張って対処する。

最大点素パスに毛が生えたくらい。

inf = 2^30にしたらオーバーフローしてビビった。2^29にしてAC

namespace MCF { //init before you use it. //inf should be 1 << 29 or less

	struct edge { int to, cap, cost, rev; };

	int V; //num of vertex
	vector<edge> G[MAX_V];
	int h[MAX_V];
	int dist[MAX_V];
	int prevv[MAX_V], preve[MAX_V];

	void init(int v) {
		V = v;
		rep(i, 0, v) G[i].clear();
	}

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

	int get(int s, int t, int f) {
		int res = 0;
		memset(h, 0, sizeof(h));
		while(f > 0) {
			priority_queue<pi, vector<pi>, greater<pi> > que;
			fill(dist, dist + V, inf);
			dist[s] = 0;
			que.push(pi(0, s));
			while(!que.empty()) {
				pi p = que.top(); que.pop();
				int v = p.sec;
				if(dist[v] < p.fst) continue;
				rep(i, 0, (int)G[v].size()) {
					edge &e = G[v][i];
					if(e.cap > 0 && 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(pi(dist[e.to], e.to));
					}
				}
			}
			if(dist[t] == inf) return -1;
			rep(v, 0, 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, M;

int main() {
	for(int q = 1; ; q++) {
		scanf("%d%d", &N, &M);
		if(N == 0 && M == 0) break;
		MCF::init(N * 2);

		rep(i, 0, M) {
			int a, b, c; 
			scanf("%d%d%d", &a, &b, &c);
			MCF::add_edge(a + N, b, 1, c);
		}

		rep(i, 0, N) MCF::add_edge(i, i + N, 1, 0);

		int ans = MCF::get(N, N - 1, 2);
		printf("Instance #%d: ", q);
		if(ans == -1) printf("Not possible\n");
		else printf("%d\n", ans);
	}
	return 0;
}

すこしTexいじったので、ブログでも使おうかと思ったけど意外にめんどくさそう。