POJ 2047 - Concert Hall Scheduling

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

概要

コンサートホールに使わせてほしいという依頼が N 個きている．

依頼は「i 日目から j 日目まで w 円で使わせてほしい」というもので， そのコンサートホールには2つの全く同じ部屋があるため， 各依頼に対してどちらかの部屋を割り当てることができる．

利益を最大にするように依頼を受けたときの利益の答える．

制約

解法

最小費用流．

最初，日にちをノードとして依頼 x, y について「x の後に y を受けることができる」ときに x.j から y.i にエッジを張ったようなグラフを作って最小費用流を求めた．

2047-1

図は Sample Input の2つ目のケース．i 日目の開始を i, 終了を i' で表現している．

これでも解ける けど，エッジの数が N^2 程度あって遅い (AOJ 1246 において，2:34 で AC した)．

そこでエッジの張りかたを変え，すべての i について i 日目から i+1 日目に容量2のエッジを張り， 各依頼について i から j に容量1，費用 -w のエッジを張るようにした． こうするとエッジの数は N+365*2 くらいに抑えられる． ある意味こっちのほうが自然なかんじはする…

2047-2

図は Sample Input の1つ目のケース．

また，どちらのグラフも多重辺を含んでいるため，Spaghetti Source さんの Primal-Dual をコピペしても解けない． capacity, flow をエッジに持たせ，さらに各エッジに逆辺の情報を持たせることで，多重辺があっても動く Primal-Dual を書いた．

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