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いじったので、ブログでも使おうかと思ったけど意外にめんどくさそう。