【最大费用最大流】【Codeforces】164C - Machine Programming-白红宇

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

阅读量：4705 次

发布时间：2019-06-10

本文共 3569 字，大约阅读时间需要 11 分钟。

题目来源：

题目大意：有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 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
           7 #include 
           
             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 
            
              kk; 22 typedef pair 
             
               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 
              
                Dist, Co; 35 deque 
               
                 Q; 36 map 
                
                  Name; 37 map 
                 
                   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 }

转载于:https://www.cnblogs.com/GXZC/archive/2012/12/22/2828739.html

你可能感兴趣的文章