首页 > 代码库 > codevs 1803 志愿者招募
codevs 1803 志愿者招募
1803 志愿者招募
2008年NOI全国竞赛申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的 主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志 愿者。经过估算，这个项目需要 N 天才能完成，其中第 i 天至少需要 Ai个人。 布布通过了解得知，一共有 M 类志愿者可以招募。其中第 i 类可以从第 Si天工 作到第 Ti 天，招募费用是每人 Ci元。新官上任三把火，为了出色地完成自己的 工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是 布布找到了你，希望你帮他设计一种最优的招募方案。
输入描述 Input Description
输入文件 employee.in 的第一行包含两个整数 N, M，表示完成项目的天数和 可以招募的志愿者的种类。 接下来的一行中包含 N 个非负整数，表示每天至少需要的志愿者人数。 接下来的 M 行中每行包含三个整数 Si, Ti, Ci，含义如上文所述。为了方便起 见，我们可以认为每类志愿者的数量都是无限多的。
输入文件 employee.out 中仅包含一个整数，表示你所设计的最优方案的总费用。
3 3
2 3 4
1 2 2
2 3 5
3 3 2
14
【样例说明】
招募 3 名第一类志愿者和 4 名第三类志愿者。
30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10；
100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均不超过 231-1。
解题：上下界费用流。
建图，第i天向第i+1天建立下界为第i天需要的人数的边，对于人的种类，可以连接ti+1 到 si 费用为ti，流量为无限的边。然后就是类似于上下界流那样，建图。建图后求最小费用流。注意由于i到i+1的边表示第i天至少得招募人数，所有就会有n+1个点。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f3f3f3f3fLL 16 using namespace std; 17 const int maxn = 100010; 18 struct arc{ 19 int to,next; 20 LL flow,cost; 21 arc(int x = 0,LL y = 0,LL z = 0,int nxt = -1){ 22 to = x; 23 flow = y; 24 cost = z; 25 next = nxt; 26 } 27 }; 28 arc e[maxn*10]; 29 int head[maxn],p[maxn],S,T,tot,n,m; 30 LL d[maxn],in[maxn]; 31 bool vis[maxn]; 32 void add(int u,int v,LL flow,LL cost){ 33 e[tot] = arc(v,flow,cost,head[u]); 34 head[u] = tot++; 35 e[tot] = arc(u,0,-cost,head[v]); 36 head[v] = tot++; 37 } 38 bool spfa(){ 39 queue<int>q; 40 for(int i = 0; i <= T; ++i){ 41 vis[i] = false; 42 d[i] = INF; 43 p[i] = -1; 44 } 45 d[S] = 0; 46 q.push(S); 47 while(!q.empty()){ 48 int u = q.front(); 49 q.pop(); 50 vis[u] = false; 51 for(int i = head[u]; ~i; i = e[i].next){ 52 if(e[i].flow && d[e[i].to] > d[u] + e[i].cost){ 53 d[e[i].to] = d[u] + e[i].cost; 54 p[e[i].to] = i; 55 if(!vis[e[i].to]){ 56 vis[e[i].to] = true; 57 q.push(e[i].to); 58 } 59 } 60 } 61 } 62 return p[T] > -1; 63 } 64 LL solve(){ 65 LL ans = 0; 66 while(spfa()){ 67 LL minv = INF; 68 for(int i = p[T]; ~i; i = p[e[i^1].to]) 69 minv = min(minv,e[i].flow); 70 for(int i = p[T]; ~i; i = p[e[i^1].to]){ 71 e[i].flow -= minv; 72 e[i^1].flow += minv; 73 ans += minv*e[i].cost; 74 } 75 } 76 return ans; 77 } 78 int main() { 79 LL tmp,w; 80 int u,v; 81 while(~scanf("%d %d",&n,&m)){ 82 memset(head,-1,sizeof(head)); 83 memset(in,0,sizeof(in)); 84 S = n + 2; 85 T = n + 3; 86 for(int i = 1; i <= n; ++i){ 87 scanf("%lld",&tmp); 88 add(i,i+1,INF-tmp,0); 89 in[i] -= tmp; 90 in[i+1] += tmp; 91 } 92 for(int i = 0; i < m; ++i){ 93 scanf("%d %d %lld",&u,&v,&tmp); 94 add(v+1,u,INF,tmp); 95 } 96 for(int i = 1; i <= n + 1; ++i) 97 if(in[i] < 0) add(i,T,-in[i],0); 98 else if(in[i] > 0) add(S,i,in[i],0); 99 printf("%lld",solve());100 }101 return 0;102 }
codevs 1803 志愿者招募