首页 > 代码库 > NOI2008 志愿者招募
NOI2008 志愿者招募
1061: [Noi2008]志愿者招募
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 1859 Solved: 1169
[Submit][Status]
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
HINT
招募第一类志愿者3名，第三类志愿者4名 30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。
Source
题解：BYVOID
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。
例如一共需要4天，四天需要的人数依次是4,2,5,3。有5类志愿者，如下表所示：
| 种类 | 1 | 2 | 3 | 4 | 5 |
| 时间 | 1-2 | 1-1 | 2-3 | 3-3 | 3-4 |
| 费用 | 3 | 4 | 3 | 5 | 6 |
设雇佣第i类志愿者的人数为X[i]，每个志愿者的费用为V[i]，第j天雇佣的人数为P[j]，则每天的雇佣人数应满足一个不等式，如上表所述，可以列出
P[1] = X[1] + X[2] >= 4
P[2] = X[1] + X[3] >= 2
P[3] = X[3] + X[4] +X[5] >= 5
P[4] = X[5] >= 3
对于第i个不等式，添加辅助变量Y[i] (Y[i]>=0) ，可以使其变为等式
P[1] = X[1] + X[2] - Y[1] = 4
P[2] = X[1] + X[3] - Y[2] = 2
P[3] = X[3] + X[4] +X[5] - Y[3] = 5
P[4] = X[5] - Y[4] = 3
在上述四个等式上下添加P[0]=0,P[5]=0，每次用下边的式子减去上边的式子，得出
① P[1] - P[0] = X[1] + X[2] - Y[1] = 4
② P[2] - P[1] = X[3] - X[2] -Y[2] +Y[1] = -2
③ P[3] - P[2] = X[4] + X[5] - X[1] - Y[3] + Y[2] =3
④ P[4] - P[3] = - X[3] - X[4] + Y[3] - Y[4] = -2
⑤ P[5] - P[4] = - X[5] + Y[4] = -3
观察发现，每个变量都在两个式子中出现了，而且一次为正，一次为负。所有等式右边和为0。接下来，根据上面五个等式构图。
- 每个等式为图中一个顶点，添加源点S和汇点T。
- 如果一个等式右边为非负整数c，从源点S向该等式对应的顶点连接一条容量为c，权值为0的有向边；如果一个等式右边为负整数c，从该等式对应的顶点向汇点T连接一条容量为c，权值为0的有向边。
- 如果一个变量X[i]在第j个等式中出现为X[i]，在第k个等式中出现为-X[i]，从顶点j向顶点k连接一条容量为∞，权值为V[i]的有向边。
- 如果一个变量Y[i]在第j个等式中出现为Y[i]，在第k个等式中出现为-Y[i]，从顶点j向顶点k连接一条容量为∞，权值为0的有向边。
构图以后，求从源点S到汇点T的最小费用最大流，费用值就是结果。
根据上面的例子可以构造出如下网络，红色的边为每个变量X代表的边，蓝色的边为每个变量Y代表的边，边的容量和权值标已经标出(蓝色没有标记，因为都是容量∞，权值0)。
在这个图中求最小费用最大流，流量网络如下图，每个红色边的流量就是对应的变量X的值。
所以，答案为43+23+3*6=36。
上面的方法很神奇得求出了结果，思考为什么这样构图。我们将最后的五个等式进一步变形，得出以下结果
① - X[1] - X[2] + Y[1] + 4 = 0
② - X[3] + X[2] + Y[2] - Y[1] - 2 = 0
③ - X[4] - X[5] + X[1] + Y[3] - Y[2] + 3 = 0
④ X[3] + X[4] - Y[3] + Y[4] - 2 = 0
⑤ X[5] - Y[4] - 3 = 0
可以发现，每个等式左边都是几个变量和一个常数相加减，右边都为0，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求
最小，所以要在X变量相对应的边上加上权值，然后求最小费用最大流。
我写的是朴素的SPFA算法求增广路的最小费用流算法，可以在题目时限内通过所有测试点。
在NOI的现场上，该题得分的平均分12.56，只有高逸涵大牛拿到了满分。不能不说这是一道难题，难就难在抽象出问题的数学模型，设计有效的算法。而信息学竞赛正朝着这个方向发展，数学建模将是解决问题的共同关键步骤。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码：
1 const inf=maxlongint; 2 type node=record 3 from,go,next,v,c:longint; 4 end; 5 var e:array[0..200000] of node; 6 pre,head,q,d,p:array[0..100000] of longint; 7 v:array[0..100000] of boolean; 8 i,j,n,m,s,t,l,r,mincost,tot,x,y,z:longint; 9 function min(x,y:Longint):longint; 10 begin 11 if x<y then exit(x) else exit(y); 12 end; 13 14 procedure ins(x,y,z,w:longint); 15 begin 16 inc(tot); 17 with e[tot] do 18 begin 19 from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot; 20 end; 21 end; 22 procedure insert(x,y,z,w:longint); 23 begin 24 ins(x,y,z,w);ins(y,x,0,-w); 25 end; 26 function spfa:boolean; 27 var i,x,y:longint; 28 begin 29 fillchar(v,sizeof(v),false); 30 for i:=s to t do d[i]:=inf; 31 l:=0;r:=1;q[1]:=s;d[s]:=0;v[s]:=true; 32 while l<r do 33 begin 34 inc(l); 35 x:=q[l];v[x]:=false; 36 i:=head[x]; 37 while i<>0 do 38 begin 39 y:=e[i].go; 40 if (e[i].v<>0) and (d[x]+e[i].c<d[y]) then 41 begin 42 d[y]:=d[x]+e[i].c; 43 pre[y]:=i; 44 if not(v[y]) then 45 begin 46 v[y]:=true; 47 inc(r); 48 q[r]:=y; 49 end; 50 end; 51 i:=e[i].next; 52 end; 53 end; 54 exit(d[t]<>inf); 55 end; 56 procedure mcf; 57 var i,tmp:longint; 58 begin 59 mincost:=0; 60 while spfa do 61 begin 62 tmp:=inf; 63 i:=pre[t]; 64 while i<>0 do 65 begin 66 tmp:=min(tmp,e[i].v); 67 i:=pre[e[i].from]; 68 end; 69 inc(mincost,tmp*d[t]); 70 i:=pre[t]; 71 while i<>0 do 72 begin 73 dec(e[i].v,tmp); 74 inc(e[i xor 1].v,tmp); 75 i:=pre[e[i].from]; 76 end; 77 end; 78 end; 79 procedure init; 80 begin 81 tot:=1; 82 readln(n,m); s:=0;t:=n+2; 83 for i:=1 to n do read(p[i]); 84 for i:=1 to n+1 do 85 begin 86 if i>1 then insert(i,i-1,inf,0); 87 if p[i]>=p[i-1] then insert(s,i,p[i]-p[i-1],0) 88 else insert(i,t,p[i-1]-p[i],0); 89 end; 90 for i:=1 to m do 91 begin 92 readln(x,y,z); 93 insert(x,y+1,inf,z); 94 end; 95 end; 96 procedure main; 97 begin 98 mincost:=0; 99 mcf;100 writeln(mincost);101 end;102 begin103 assign(input,‘input.txt‘);assign(output,‘output.txt‘);104 reset(input);rewrite(output);105 init;106 main;107 close(input);close(output);108 end.