POJ 2135 - Farm Tour

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

概要

頂点数 \(N\)、辺数 \(M\) の重みつき無向グラフが与えられる。 頂点 1 から頂点 \(N\) まで行き、そこからまた頂点 1 まで戻るような経路を考える。 ただし、行きと帰りで同じ辺を使ってはならない。 このときの最短経路を答える。

制約

解法

スタートからゴールまで辺を共有しない最短経路を2つ見つければよいので、 各辺の容量を1に設定してスタートからゴールまで2の流量を流して最小費用流を求めればいい。

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 static const int MAXN = 1000;
 6 
 7 template <class Flow, class Cost>
 8 struct edge/*{{{*/
 9 {
10   int index;
11   Flow capacity, flow;
12   Cost cost;
13   int back;
14   edge(int i, Flow c, Cost d, int b) : index(i), capacity(c), flow(0), cost(d), back(b) {}
15 };/*}}}*/
16 
17 template <class Flow, class Cost>
18 void make_edge(vector<edge<Flow, Cost> > *g, int src, int dst, Flow c, Cost d)/*{{{*/
19 {
20   const int i = g[src].size(), j = g[dst].size();
21   g[src].push_back(edge<Flow, Cost>(dst, c, d, j));
22   g[dst].push_back(edge<Flow, Cost>(src, 0, -d, i));
23 }/*}}}*/
24 
25 // O(V^2 U C) where
26 //  U = sum of capacity
27 //  C = sum of cost
28 template <class Flow, class Cost>
29 pair<Flow, Cost>
30 primal_dual(vector<edge<Flow, Cost> > *g, int N, int source, int sink, int max_flow)/*{{{*/
31 {
32   pair<Flow, Cost> total;
33   static Cost h[MAXN], dist[MAXN];
34   static pair<int,int> parent[MAXN];
35   for (Flow f = max_flow; f > 0; ) {
36     fill_n(dist, N, 90000000);
37     dist[source] = 0;
38     fill_n(parent, N, make_pair(-1, -1));
39     priority_queue<pair<Cost,int> > q;
40     q.push(make_pair(0, source));
41     while (!q.empty()) {
42       const int n = q.top().second;
43       const Cost c = -q.top().first;
44       q.pop();
45       if (dist[n] < c) {
46         continue;
47       }
48       for (typename vector<edge<Flow, Cost> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
49         if (it->capacity - it->flow > 0) {
50           const Cost c2 = c + it->cost + h[n] - h[it->index];
51           if (c2 < dist[it->index]) {
52             dist[it->index] = c2;
53             parent[it->index] = make_pair(n, it - g[n].begin());
54             q.push(make_pair(-c2, it->index));
55           }
56         }
57       }
58     }
59     if (parent[sink].first == -1) {
60       break;
61     }
62 
63     Flow e = f;
64     for (int i = sink; i != source; i = parent[i].first) {
65       const edge<Flow, Cost>& x = g[parent[i].first][parent[i].second];
66       e = min(e, x.capacity - x.flow);
67     }
68     for (int i = sink; i != source; i = parent[i].first) {
69       edge<Flow, Cost>& x = g[parent[i].first][parent[i].second];
70       total.second += e * x.cost;
71       x.flow += e;
72       g[x.index][x.back].flow -= e;
73     }
74     f -= e;
75     total.first += e;
76     for (int i = 0; i < N; i++) {
77       h[i] += dist[i];
78     }
79   }
80 
81   return total;
82 }/*}}}*/
83 
84 int main()
85 {
86   int N, M;
87   cin >> N >> M;
88   static vector<edge<int,int> > g[MAXN];
89   for (int i = 0; i < M; i++) {
90     int u, v, c;
91     cin >> u >> v >> c;
92     --u;  --v;
93     make_edge(g, u, v, 1, c);
94     make_edge(g, v, u, 1, c);
95   }
96   cout << primal_dual(g, N, 0, N-1, 2).second << endl;
97   return 0;
98 }
poj/2135.cc