AOJ 2304 - Reverse Roads

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

概要

ノード数 N，エッジ数 M の有向グラフが与えられる． このうち何本かのエッジの向きを変えて S から T への最大流を最大化したい． そのときの最大流と，向きを変えたエッジを出力する．

制約

• 2 <= N <= 300
• 0 <= M <= min(1000, N(N-1)/2)

解法

無向グラフと見て最大流を求め，そのときのフローと最初に与えられた有向グラフを比較して逆方向に流れているところのエッジを出力する．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <limits>
 5 using namespace std;
 6 
 7 template <typename T>
 8 pair<T, vector<vector<T> > >
 9 edmonds_karp(const vector<vector<T> >& capacity, int source, int sink)/*{{{*/
10 {
11   const int N = capacity.size();
12   vector<vector<T> > flow(N, vector<T>(N, 0));
13   T max_flow = 0;
14 
15   while (true) {
16     vector<int> parent(N, -1);
17     queue<int> q;
18     q.push(source);
19 
20     while (!q.empty() && parent[sink] < 0) {
21       const int v = q.front();
22       q.pop();
23 
24       for (int u = 0; u < N; u++) {
25         if (parent[u] < 0 && capacity[v][u] - flow[v][u] > 0) {
26           parent[u] = v;
27           if (u == sink) {
28             break;
29           }
30           q.push(u);
31         }
32       }
33     }
34 
35     if (parent[sink] < 0) {
36       break;
37     }
38 
39     T aug = numeric_limits<T>::max();
40     for (int v = sink; v != source; v = parent[v]) {
41       const int u = parent[v];
42       aug = min(aug, capacity[u][v] - flow[u][v]);
43     }
44     max_flow += aug;
45     for (int v = sink; v != source; v = parent[v]) {
46       const int u = parent[v];
47       flow[u][v] += aug;
48       flow[v][u] -= aug;
49     }
50   }
51 
52   return make_pair(max_flow, flow);
53 }/*}}}*/
54 
55 int main()
56 {
57   int N, M;
58   cin >> N >> M;
59   vector<vector<int> > capacity(N, vector<int>(N, 0));
60   vector<pair<int,int> > edges;
61   for (int i = 0; i < M; i++) {
62     int u, v;
63     cin >> u >> v;
64     --u;  --v;
65     ++capacity[u][v];
66     ++capacity[v][u];
67     edges.push_back(make_pair(u, v));
68   }
69   int S, T;
70   cin >> S >> T;
71   --S;  --T;
72 
73   const pair<int, vector<vector<int> > > r = edmonds_karp(capacity, S, T);
74   cout << r.first << endl;
75   vector<int> ans;
76   const vector<vector<int> >& flow = r.second;
77   for (int i = 0; i < M; i++) {
78     if (flow[edges[i].second][edges[i].first] > 0) {
79       ans.push_back(i);
80     }
81   }
82   cout << ans.size() << endl;
83   for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
84     cout << *it+1 << endl;
85   }
86 
87   return 0;
88 }