AOJ 2293 - Dangerous Tower

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

解法

2011/Practice/夏合宿/講評 - ACM-ICPC Japanese Alumni Group を参照．

解説スライドにあるように，横の長さが異なるように積み木を選べばそれらをすべて使える点に注目して最小費用流の問題に落とす．

積み木 i の使い方は

の3つ．これらを

で表す．

同じ横の長さは1つまでしか使えないことを，横の長さのノードからシンクへの容量1のエッジで表す． ダミーノードからシンクへのエッジの容量は無限大． 

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <limits>
  6 using namespace std;
  7 static const int MAXN = 3010;
  8 
  9 template <class Flow, class Cost>
 10 struct node
 11 {
 12   int index;
 13   Flow capacity;
 14   Cost cost;
 15   node(int i, Flow c, Cost d) : index(i), capacity(c), cost(d) {}
 16 };
 17 
 18 template <class Flow, class Cost>
 19 node<Flow, Cost> make_node(int i, Flow c, Cost d) { return node<Flow, Cost>(i, c, d); }
 20 
 21 template <class Flow, class Cost>
 22 pair<Flow, Cost>
 23 primal_dual(const vector<node<Flow, Cost> > *g, int N, int source, int sink)/*{{{*/
 24 {
 25   static Flow capacity[MAXN][MAXN], flow[MAXN][MAXN];
 26   static Cost cost[MAXN][MAXN];
 27   for (int i = 0; i < N; i++) {
 28     for (typename vector<node<Flow, Cost> >::const_iterator it(g[i].begin()); it != g[i].end(); ++it) {
 29       capacity[i][it->index] += it->capacity;
 30       cost[i][it->index] += it->cost;
 31     }
 32   }
 33   pair<Flow, Cost> total;
 34   static Cost h[MAXN], dist[MAXN];
 35   static int parent[MAXN];
 36   for (Flow f = numeric_limits<Flow>::max(); f > 0; ) {
 37     fill_n(dist, N, 1000000);
 38     dist[source] = 0;
 39     fill_n(parent, N, -1);
 40     priority_queue<pair<Cost,int> > q;
 41     q.push(make_pair(0, source));
 42     while (!q.empty()) {
 43       const int n = q.top().second;
 44       const Cost c = -q.top().first;
 45       q.pop();
 46       if (dist[n] < c) {
 47         continue;
 48       }
 49       for (typename vector<node<Flow, Cost> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 50         if (capacity[n][it->index] - flow[n][it->index] > 0) {
 51           const Cost c2 = c + cost[n][it->index] + h[n] - h[it->index];
 52           if (c2 < dist[it->index]) {
 53             dist[it->index] = c2;
 54             parent[it->index] = n;
 55             q.push(make_pair(-c2, it->index));
 56           }
 57         }
 58       }
 59     }
 60     if (parent[sink] == -1) {
 61       break;
 62     }
 63 
 64     Flow e = f;
 65     for (int i = sink; i != source; i = parent[i]) {
 66       e = min(e, capacity[parent[i]][i] - flow[parent[i]][i]);
 67     }
 68     for (int i = sink; i != source; i = parent[i]) {
 69       total.second += e * cost[parent[i]][i];
 70       flow[i][parent[i]] -= e;
 71       flow[parent[i]][i] += e;
 72     }
 73     f -= e;
 74     total.first += e;
 75     for (int i = 0; i < N; i++) {
 76       h[i] += dist[i];
 77     }
 78   }
 79 
 80   return total;
 81 }/*}}}*/
 82 
 83 int main()
 84 {
 85   int N;
 86   scanf("%d", &N);
 87   static pair<int,int> blocks[1000];
 88   vector<int> v;
 89   for (int i = 0; i < N; i++) {
 90     scanf("%d %d", &blocks[i].first, &blocks[i].second);
 91     v.push_back(blocks[i].first);
 92     v.push_back(blocks[i].second);
 93   }
 94   sort(v.begin(), v.end());
 95 
 96   static vector<node<int, long long> > g[MAXN];
 97   const int source = N + v.size();
 98   const int sink = source + 1;
 99   const int dummy = sink + 1;
100   for (int i = 0; i < N; i++) {
101     const long long a = blocks[i].first, b = blocks[i].second;
102     const int j = lower_bound(v.begin(), v.end(), a) - v.begin();
103     const int k = lower_bound(v.begin(), v.end(), b) - v.begin();
104     g[source].push_back(make_node(i, 1, 0LL));
105     g[i].push_back(make_node(source, 0, 0LL));
106 
107     g[i].push_back(make_node(dummy, 1, 0LL));
108     g[dummy].push_back(make_node(i, 0, 0LL));
109 
110     g[i].push_back(make_node(N+j, 1, -b));
111     g[N+j].push_back(make_node(i, 0, b));
112     if (b != a) {
113       g[i].push_back(make_node(N+k, 1, -a));
114       g[N+k].push_back(make_node(i, 0, a));
115     }
116   }
117   for (vector<int>::size_type i = 0; i < v.size(); i++) {
118     g[N+i].push_back(make_node(sink, 1, 0LL));
119     g[sink].push_back(make_node(N+i, 0, 0LL));
120   }
121   g[dummy].push_back(make_node(sink, N, 0LL));
122 
123   printf("%lld\n", -primal_dual(g, dummy+1, source, sink).second);
124   return 0;
125 }
aoj/2293.cc