主题

主题

 
   

1061: [Noi2008]志愿者招募

Description

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

Input

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

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

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

Output

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

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

14

HINT

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


个人解法:

假设第i个计划招募了X[i]个人。而第i天需要A[i]个人。

那么我们会满足一些形如线性规划的式子。这些式子有一定的特征,待会会用到。

拿样例来说:

X[1]>=A[1]=2

X[1]+X[2]>=A[2]=3

X[2]+X[3]>=A[3]=5

我们尝试认为加入一些正变量,假设这些变量为Y[i]。

那么转换为m个方程:

X[1]+Y[1]=2

X[1]+X[2]+Y[2]=3

X[2]+X[3]+Y[3]=5

那么对于这个形如线性规划的式子,我们对式子做差分,用第i个式子减去第i-1个式子(如果m(样例中m=3)个式子,做到m+1(样例中即为4)次差分),得到m+1个差分式子:

X[1]+Y[1]=2

X[2]+Y[2]-Y[1]=1

X[3]+Y[3]-X[1]-Y[2]=2

-X[2]-X[3]-Y[3]=-5

我们把第i个差分式子右边的常数定义为C[i]。

接下来我们发现每一个变量只出现了2次。并且一正一负。

  • 试问:为什么每一个变量只出现了两次?

  1. 对于X变量,我们知道X[i]对应的是i计划。i计划涵盖的[l..r]区间都会有X[i]的存在,即[l..r]的所有方程均有X变量的存在。那么在差分数组中,一个区间就会变为两个点l与r+1。由此X变量只会出现两次。

  2. 对于Y变量,我们知道Y[i]对应的是i这一个式子。只有在第i个差分式子与第i+1个差分式子存在Y变量。由此Y变量也只会出现两次。

  • 至于为什么一正一负,就不必赘述了。

那么观察这些差分式子。

换一种思考方式:

我们把等号“=”视为网络流的入流与出流相等。

我们建立m+1个点,分别代表m+1个差分式子。

  • 如果右边常数C[i]为正,我们从S 向 这个式子对应的点 连一条<C[i]/0>的边。如果右边常数C[i]为负,我们从 这个式子对应的点 向 T 连一条<-C[i]/0>的边。常数正负也就是意味着补充或者流出流量。

  • 如果在i式子中出现了某一个X变量为+X[k],j式子中出现了同一X变量为-X[k],那么从i式子向j式子连一条<正无穷/Cost>的边。正无穷意味着可以补充或者流出无限的流,cost意味着通过这种方式(招募人员)补充流需要付出的代价。

  • 如果在i式子中出现了某一个Y变量为+Y[k],j式子中出现了同一Y变量为-Y[k],那么从i式子向j式子连一条<正无穷/0>的边。正无穷意味着Y变量是可以任意大小,进行补充或者流出无限的流,并且不花费代价。

这样跑出最小的费用流,就是我们目标函数的最小值。


代码如下:

https://code.csdn.net/snippets/2145356

由于可能会出现相同的招募区间[l..r]然而代价可能不同,于是意味着可能两个点之间会有多条边。理论上我们取最小的即可。但是某锟告诉我一个小技巧,可以脱离矩阵,直接使用链表。

于是重新修改了费用流的模板。


本蒟的拓展与思考

以上内容参考https://www.byvoid.com/blog/noi-2008-employee/#more-916,大概他的叙述比我的清楚多了。

这个方法是否可以拓展到任意线性规划中?

  • 每个变量只出现两次,且一正一负的限制

如果对于一个X[i]出现了多次,那么我们将不好连边了。也许我们可以建一个虚点——之后把所有含有+X[i]的式子连边到此虚点,再从此虚点连边到所有含有-X[i]的式子。

  • 变量系数不为1

那么相当于一个点可能需要连出多条边。也许我们可以尝试把多条边一起带上。

(以上纯为本蒟瞎想如果有某master见了可以留言)

 
 
评论
 
 
热度(1)