【最大费用最大流】【Codeforces】164C Machine Programming

题目来源：http://www.codeforces.com/problemset/problem/164/C

题目大意：有N(1 <= N <= 1000)个任务要用K(1 <= K <= 50)台机器完成，每个任务持续一段时间Si ~ Si + Ti - 1，每个任务可以获利Ci，(1 ≤ Si , Ti ≤ 10⁹, 1 ≤ Ci ≤ 10⁶) 。每台机器同一时间内只能处理至多1个任务。满足以上限制条件，求这K台机器能取得的最大利润是多少？

题目解析：从贪心角度看，如果存在多个时间不相交的任务，那么这些任务只需要1台机器去完成。因此，每台机器处理的就是这样的一系列不相交的任务。那么对于时间相交的任务，就需要用多台机器去完成。一共有K台机器，那么问题转化为求K条不相交任务集合，使得总获利最大。

本题和《线性规划与网络流24题 -- 最长 k 可重区间集》建模方法一模一样。将所有任务的时间离散化，编号为1..L。设立源点S和汇点T，建立有向边S->1，容量为K，费用为0；（表示最多有K条不相交任务集合）建立有向边L->T，容量为INF，费用为0；建立有向边I(1 ~ L - 1)->I + 1，容量为INF，费用为0；对于每个任务的时间Si 和 Si + Ti - 1 所对应的编号 X和Y，建立有向边X->Y，容量为1，费用为-Ci。求最小费用最大流。

模型的理解：每个任务限制容量为1，表示只被完成1次，然后获利就是这条边的费用，写成负数是为了求最小费用，实际原问题属于最大费用最大流。并且以时间为端点，不相交的任务可以用同一台机器去完成，相交的任务只能用多台机器去完成。

　　　　　　另外题目要求的是路径，而不是最大费用那个值。因此要把费用为负数的满流边记录下来，最后输出。

代码如下：

  1 #include <iostream>
  2 #include <climits>
  3 #include <utility>
  4 #include <vector>
  5 #include <deque>
  6 #include <map>
  7 #include <algorithm>
  8 
  9 #define rep(i, x) for (int i = 1; i <= x; i ++)
 10 #define rept(i, x) for (int i = 0; i <= x; i ++)
 11 #define tr(i, x) for (typeof(x.begin()) i = x.begin(); i != x.end(); i ++)
 12 #define all(x) x.begin(), x.end()
 13 #define pb push_back
 14 #define ppf pop_front()
 15 #define mp make_pair
 16 
 17 using namespace std;
 18 
 19 const int Maxn = 2001, INF = INT_MAX;
 20 
 21 typedef pair <int, int> kk;
 22 typedef pair <kk, int> kkk;
 23 
 24 struct edge
 25 {
 26     int v, c, w;
 27     edge* next, * op;
 28     edge(int _v, int _c, int _w, edge* _next) :
 29         v(_v), c(_c), w(_w), next(_next) {}
 30 }* E[Maxn], * PE[Maxn];
 31 
 32 bool hash[Maxn];
 33 int S, T, N, K, X[Maxn], Y[Maxn], W[Maxn], P[Maxn];
 34 vector <int> Dist, Co;
 35 deque <int> Q;
 36 map <int, int> Name;
 37 map <kkk, int> Task;
 38 
 39 void Print()
 40 {
 41     rept(i, T)
 42         for (edge* j = E[i]; j; j = j -> next)
 43         {
 44             if (j -> w < 0 && j -> c == 0)
 45                 Task[mp(mp(i, j -> v), j -> w)] ++;
 46         }
 47     int Count = 0;
 48     rep(i, N)
 49     {
 50         if (i != 1) cout << " ";
 51         int x = Name[X[i]], y = Name[Y[i]];
 52         kkk tmp = mp(mp(x, y), -W[i]);
 53         if (Task[tmp] > 0)
 54         {
 55             cout << 1; Task[tmp] --;
 56         }
 57         else cout << 0;
 58     }
 59     cout << endl;
 60 }
 61 
 62 void Augment()
 63 {
 64     int add = INF;
 65     for (int i = T; i != S; i = P[i])
 66     {
 67         if (PE[i] -> c < add) add = PE[i] -> c;
 68     }
 69     for (int i = T; i != S; i = P[i])
 70     {
 71         PE[i] -> c -= add;
 72         PE[i] -> op -> c += add;
 73     }
 74 }
 75 
 76 bool SPFA()
 77 {
 78     Dist.assign(T + 1, INF); Dist[S] = 0; Q.pb(S);
 79     while (Q.size())
 80     {
 81         int i = Q.front(); Q.ppf; hash[i] = false;
 82         for (edge* j = E[i]; j; j = j -> next)
 83         {
 84             int v = j -> v;
 85             if (j -> c && Dist[i] + j -> w < Dist[v])
 86             {
 87                 Dist[v] = Dist[i] + j -> w;
 88                 P[v] = i; PE[v] = j;
 89                 if (!hash[v])
 90                 {
 91                     hash[v] = true;
 92                     Q.pb(v);
 93                 }
 94             }
 95         }
 96     }
 97     return Dist[T] != INF;
 98 }
 99 
100 void SPFAFlow()
101 {
102     while (SPFA()) Augment();
103 }
104 
105 inline void edgeAdd(int x, int y, int c, int w)
106 {
107     E[x] = new edge(y, c, w, E[x]);
108     E[y] = new edge(x, 0, -w, E[y]);
109     E[x] -> op = E[y]; E[y] -> op = E[x];
110 }
111 
112 void Graph()
113 {
114     S = 0; T = Co.size() + 1;
115     edgeAdd(S, 1, K, 0); edgeAdd(Co.size(), T, K, 0);
116     rep(i, Co.size() - 1) edgeAdd(i, i + 1, INF, 0);
117     rep(i, N) edgeAdd(Name[X[i]], Name[Y[i]], 1, -W[i]);
118 }
119 
120 void Init()
121 {
122     cin >> N >> K;
123     rep(i, N)
124     {
125         cin >> X[i] >> Y[i] >> W[i]; Y[i] += X[i];
126         Co.pb(X[i]); Co.pb(Y[i]);
127     }
128     sort(all(Co));
129     Co.erase(unique(all(Co)), Co.end());
130     tr(i, Co) Name[* i] = i - Co.begin() + 1;
131 }
132 
133 int main()
134 {
135     Init();
136     Graph();
137     SPFAFlow();
138     Print();
139     return 0;
140 }