[费用流][NOI2008]志愿者招募

志愿者招募

题目描述

　　申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难

题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要

Ai 个人。布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用

是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这

并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

输入

　　第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含N 个非负

整数，表示每天至少需要的志愿者人数。接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了

方便起见，我们可以认为每类志愿者的数量都是无限多的。

输出

　仅包含一个整数，表示你所设计的最优方案的总费用。

样例输入

样例输出

提示

1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均不超过2^31-1

题解个人觉得这篇写得挺好的（其实因为自己也没有完全弄清楚+懒qwqq: 点击我看题解(*/ω＼*)

蒟蒻的超慢代码：

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 
  6 const int Maxv = 10010, INF = 0x6ffffff, M = 10005; 
  7 int Head[Maxv], d[Maxv], from[Maxv], cost[Maxv], a[Maxv], s, n, m, t, cnt = 1; 
  8 bool inq[Maxv]; 
  9 struct edge{
 10     int from, to, w, c, next; 
 11 }e[Maxv << 2]; 
 12 
 13 inline int read(){
 14     int x = 0, f = 1; 
 15     char c = getchar(); 
 16     while (c < '0' || c > '9') {
 17         if (c == '-') {
 18             f = -1; 
 19         }
 20         c = getchar(); 
 21     }
 22     while (c >= '0' && c <= '9') {
 23         x = x * 10 + c - '0';
 24         c = getchar();
 25     }
 26     return x * f; 
 27 }
 28 
 29 void Add(int u, int v, int w, int c){
 30     cnt++; 
 31     e[cnt].from = u; 
 32     e[cnt].to = v; 
 33     e[cnt].w = w; 
 34     e[cnt].c = c; 
 35     e[cnt].next = Head[u]; 
 36     Head[u] = cnt; 
 37 }
 38 
 39 void Add_Edge(int u, int v, int w, int c){
 40     Add(u, v, w, c); 
 41     Add(v, u, 0, -c); 
 42 }
 43 
 44 bool spfa(){
 45     for (int i = 1; i <= t; i++) {
 46         d[i] = INF; 
 47     }
 48     memset(inq, false, sizeof(inq)); 
 49     std::queue<int> Q;
 50     Q.push(s); 
 51     d[s] = 0; 
 52     inq[s] = true; 
 53     while (!Q.empty()) {
 54         int u = Q.front(); 
 55         Q.pop(); 
 56         inq[u] = false; 
 57         for (int i = Head[u]; i; i = e[i].next) {
 58             if (e[i].w > 0 && d[e[i].to] > d[u] + e[i].c) {
 59                 d[e[i].to] = d[u] + e[i].c; 
 60                 from[e[i].to] = i; 
 61                 if (!inq[e[i].to]) {
 62                     Q.push(e[i].to); 
 63                     inq[e[i].to] = true;   
 64                 }                 
 65             }
 66         }
 67     }
 68     return d[t] != INF; 
 69 }
 70 
 71 int MCMF(){
 72     int Ans = 0; 
 73     while (spfa()) {
 74         int x = INF; 
 75         for (int i = from[t]; i; i = from[e[i].from]) {
 76             x = std::min(x, e[i].w); 
 77         }
 78         Ans += d[t] * x; 
 79         for (int i = from[t]; i; i = from[e[i].from]) {
 80             e[i].w -= x; 
 81             e[i ^ 1].w += x; 
 82         }
 83     }
 84     return Ans; 
 85 }
 86 
 87 int main(){
 88     memset(Head, 0, sizeof(Head)); 
 89     int x, y, ans; 
 90     n = read(); 
 91     m = read(); 
 92     s = n + 2; 
 93     t = s + 1; 
 94     for (int i = 1; i <= n; i++) {
 95         a[i] = read(); 
 96     }
 97     for (int i = 1; i <= m; i++) {
 98         x = read(); 
 99         y = read(); 
100         cost[i] = read(); 
101         Add_Edge(x, y + 1, INF, cost[i]); 
102     }
103     a[0] = a[n + 1] = 0; 
104     for (int i = 1; i <= n + 1; i++) {
105         int tmp = a[i] - a[i - 1];  
106         if (tmp >= 0) {
107             Add_Edge(s, i, tmp, 0);  
108         }
109         else {
110             Add_Edge(i, t, -tmp, 0);
111         }  
112     }
113     for (int i = 1; i <= n; i++) {
114         Add_Edge(i + 1, i, INF, 0); 
115     }
116     printf("%d
", MCMF()); 
117     return 0; 
118 }