[NOI2008]志愿者招募

转载自byvoid

这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。

构造网络是该题的关键，以下面一个例子说明构图的方法和解释。

例如一共需要 4 天，四天需要的人数依次是 4, 2, 5, 3。有 5 类志愿者，如下表所示：

设雇佣第𝑖类志愿者的人数为𝑋𝑖，每个志愿者的费用为𝑉𝑖，第𝑗天雇佣的人数为𝑃𝑗，则每天的雇佣人数应满足一个不等式，如上表所述，可以列出

对于第𝑖个不等式，添加辅助变量𝑌𝑖(𝑌𝑖≤0)，可以使其变为等式

在上述四个等式上下添加𝑃0=0,𝑃5=0，每次用下边的式子减去上边的式子，得出

观察发现，每个变量都在两个式子中出现了，而且一次为正，一次为负。所有等式右边和为0。

接下来，根据上面五个等式构图。

每个等式为图中一个顶点，添加源点𝑆和汇点𝑇。

如果一个等式右边为非负整数𝑐，从源点𝑆向该等式对应的顶点连接一条容量为𝑐、权值为0的有向边；如果一个等式右边为负整数𝑐，从该等式对应的顶点向汇点𝑇连接一条容量为𝑐、权值为0的有向边。

如果一个变量𝑋𝑖在第𝑗个等式中出现为𝑋𝑖，在第𝑘个等式中出现为−𝑋𝑖，从顶点𝑗向顶点𝑘连接一条容量为∞、权值为𝑉𝑖的有向边。

如果一个变量𝑌𝑖在第𝑗个等式中出现为𝑌𝑖，在第𝑘个等式中出现为−𝑌𝑖，从顶点𝑗向顶点𝑘连接一条容量为∞、权值为0的有向边。

构图以后，求从源点𝑆到汇点𝑇的最小费用最大流，费用值就是结果。

根据上面的例子可以构造出如下网络，红色的边为每个变量𝑋代表的边，蓝色的边为每个变量𝑌代表的边，边的容量和权值已经标出（蓝色没有标记，因为都是容量∞、权值0）。

在这个图中求最小费用最大流，流量网络如下图，每个红色边的流量就是对应的变量𝑋的值。

所以，答案为4×3+2×3+3×6=36。

上面的方法很神奇地求出了结果，思考为什么这样构图。我们将最后的五个等式进一步变形，得出以下结果

可以发现，每个等式左边都是几个变量和一个常数相加减，右边都为0，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。

每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。

因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求∑𝑀𝑖=1𝑋𝑖⋅𝑉𝑖最小，所以要在𝑋变量相对应的边上加上权值，然后求最小费用最大流。

然而在 NOI 的现场上，该题得分的平均分12.56，只有高逸涵大牛拿到了满分。

不能不说这是一道难题，难就难在抽象出问题的数学模型，设计有效的算法。而信息学竞赛正朝着这个方向发展，数学建模将是解决问题的共同关键步骤。

Problem

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。

布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。

经过估算，这个项目需要𝑁天才能完成，其中第𝑖天至少需要𝐴𝑖个人。

布布通过了解得知，一共有𝑀类志愿者可以招募。其中第𝑖类可以从第𝑆𝑖天工作到第𝑇𝑖天，招募费用是每人𝐶𝑖元。

新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！

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

Input

第一行包含两个整数𝑁,𝑀，表示完成项目的天数和可以招募的志愿者的种类。

接下来的一行中包含𝑁个非负整数，表示每天至少需要的志愿者人数。

接下来的𝑀行中每行包含三个整数𝑆𝑖,𝑇𝑖,𝐶𝑖，含义如上文所述。

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

Output

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

Sample Input

1
3 3
2
2 3 4
3
1 2 2
4
2 3 5
5
3 3 2

Sample Output

1
14

Hint

1≤𝑁≤1000，1≤𝑀≤10000，题目中其他所涉及的数据均不超过231−1。

Code

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <queue>
6
#define inf 0x3F3F3F3F
7
using namespace std;
8
struct Node
9
{
10
  int to,next,v,c;
11
}e[100005];
12
int S,T,ans,a[1005],h[1005],d[1005],pre[1005],cnt=1;
13
bool vis[1005];
14
inline void Addedge(int x,int y,int v,int c)
15
{
16
  e[++cnt]=(Node){y,h[x],v,c};h[x]=cnt;
17
  e[++cnt]=(Node){x,h[y],0,-c};h[y]=cnt;
18
  return;
19
}
20
inline bool SPFA()
21
{
22
  int i,x,y;
23
  queue<int>q;q.push(S);
24
  memset(d,0x3F,sizeof(d));d[S]=0;
25
  while(!q.empty())
26
  {
27
    x=q.front();q.pop();
28
    vis[x]=false;
29
    for(i=h[x];i;i=e[i].next)
30
    {
31
      y=e[i].to;
32
      if(e[i].v&&d[y]>d[x]+e[i].c)
33
      {
34
        d[y]=d[x]+e[i].c;
35
        pre[y]=i;
36
        if(!vis[y]){q.push(y);vis[y]=true;}
37
      }
38
    }
39
  }
40
  return d[T]<inf;
41
}
42
inline void Adjust()
43
{
44
  int i,j=T,delta=inf;
45
  while(pre[j])
46
  {
47
    i=pre[j];
48
    if(e[i].v<delta)delta=e[i].v;
49
    j=e[i^1].to;
50
  }
51
  ans+=delta*d[T];j=T;
52
  while(pre[j])
53
  {
54
    i=pre[j];
55
    e[i].v-=delta;
56
    e[i^1].v+=delta;
57
    j=e[i^1].to;
58
  }
59
  return;
60
}
61
int main(void)
62
{
63
  int i,x,y,v,n,m;
64
  scanf("%d%d",&n,&m);
65
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
66
  for(i=1;i<=m;++i)
67
  {
68
    scanf("%d%d%d",&x,&y,&v);
69
    Addedge(x,y+1,inf,v);
70
  }
71
  S=n+2;T=n+3;
72
  for(i=1;i<=n+1;++i)
73
  {
74
    v=a[i]-a[i-1];
75
    if(v>=0)Addedge(S,i,v,0);
76
    else Addedge(i,T,-v,0);
77
  }
78
  for(i=1;i<=n;++i)Addedge(i+1,i,inf,0);
79
  while(SPFA())Adjust();
80
  printf("%d\n",ans);
81
  return 0;
82
}