POJ 3614 - Sunscreen

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

概要

C 頭の牛がおり，それぞれ SPF の値が minSPF[i] 以上 maxSPF[i] 以下の日焼止めを必要としている． 日焼止めは L 個あり，それぞれ SPF の値は SPF[i] で，cover[i] 頭の牛に塗ることができる．

このとき，最大で何頭の牛の要求を満たせるかを答える．

制約

解法

普通(?)に最大流だけど，ノード数が最大で V = C+L+2 = 5002，エッジ数が最大で E = C + C*L + L = 6,255,000 と大きめなので実装に注意が要る．

アルゴリズムは Dinic を使って TLE を回避し，グラフは隣接リストで表現して容量やフローも V * V の配列ではなくエッジに持たせるようにして MLE を回避した．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 static const int MAXN = 2500 + 2500 + 2;
  7 static const int INF = 10000000;
  8 
  9 template <class Flow>
 10 struct edge
 11 {
 12   int id;
 13   Flow capacity, flow;
 14   int back;
 15   edge(int i, Flow c, int b) : id(i), capacity(c), flow(0), back(b) {}
 16 };
 17 
 18 template <class Flow>
 19 void make_edge(vector<edge<Flow> > *g, int src, int dst, Flow c)
 20 {
 21   const int i = g[src].size(), j = g[dst].size();
 22   g[src].push_back(edge<Flow>(dst, c, j));
 23   g[dst].push_back(edge<Flow>(src, 0, i));
 24 }
 25 
 26 template <class Flow>
 27 Flow dinic_augment(vector<edge<Flow> > *g, int N, int *level, bool *finished, int u, int sink, int cur)/*{{{*/
 28 {
 29   if (u == sink || cur == 0) {
 30     return cur;
 31   }
 32   if (finished[u]) {
 33     return 0;
 34   }
 35   finished[u] = true;
 36   for (typename vector<edge<Flow> >::iterator it = g[u].begin(); it != g[u].end(); ++it) {
 37     const int v = it->id;
 38     if (it->capacity - it->flow > 0 && level[v] > level[u]) {
 39       const int f = dinic_augment(g, N, level, finished, v, sink, min(cur, it->capacity - it->flow));
 40       if (f > 0) {
 41         it->flow += f;
 42         g[v][it->back].flow -= f;
 43         finished[u] = false;
 44         return f;
 45       }
 46     }
 47   }
 48   return 0;
 49 }/*}}}*/
 50 template <class Flow>
 51 Flow dinic(vector<edge<Flow> > *g, int N, int source, int sink)/*{{{*/
 52 {
 53   Flow max_flow = 0;
 54 
 55   while (true) {
 56     static int level[MAXN];
 57     fill_n(level, N, -1);
 58     level[source] = 0;
 59     queue<int> q;
 60     q.push(source);
 61 
 62     int d = N;
 63     while (!q.empty() && level[q.front()] < d) {
 64       const int u = q.front();
 65       q.pop();
 66 
 67       if (u == sink) {
 68         d = level[u];
 69       }
 70       for (typename vector<edge<Flow> >::iterator it = g[u].begin(); it != g[u].end(); ++it) {
 71         const int v = it->id;
 72         if (level[v] < 0 && it->capacity - it->flow > 0) {
 73           q.push(v);
 74           level[v] = level[u] + 1;
 75         }
 76       }
 77     }
 78 
 79     static bool finished[MAXN];
 80     fill_n(finished, N, false);
 81     bool updated = false;
 82     while (true) {
 83       const int f = dinic_augment(g, N, level, finished, source, sink, INF);
 84       if (f == 0) {
 85         break;
 86       }
 87       max_flow += f;
 88       updated = true;
 89     }
 90 
 91     if (!updated) {
 92       break;
 93     }
 94   }
 95 
 96   return max_flow;
 97 }/*}}}*/
 98 
 99 int main()
100 {
101   int C, L;
102   scanf("%d %d", &C, &L);
103   static pair<int,int> cows[2500];
104   static vector<edge<int> > g[MAXN];
105   const int source = C+L, sink = source+1;
106   for (int i = 0; i < C; i++) {
107     scanf("%d %d", &cows[i].first, &cows[i].second);
108     make_edge(g, i, sink, 1);
109   }
110   for (int j = 0; j < L; j++) {
111     int s, p;
112     scanf("%d %d", &s, &p);
113     make_edge(g, source, C+j, p);
114     for (int i = 0; i < C; i++) {
115       if (cows[i].first <= s && s <= cows[i].second) {
116         make_edge(g, C+j, i, 1);
117       }
118     }
119   }
120   printf("%d\n", dinic(g, C+L+2, source, sink));
121   return 0;
122 }
poj/3614.cc