AC. 梦想

frank_c1

[ZJOI 2013] 防守战线

发布于2016年03月05日 | 4条评论 | 1,318阅读 | 单纯形

题目描述

战线可以看作一个长度为n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i 号位置上建一座塔有Ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm],在第i 个区间的范围内要建至少Di 座塔。求最少花费。

输入格式

第一行为两个数n, m。

接下来一行,有n 个数,描述C 数组。

接下来m 行,每行三个数Li,Ri,Di,描述一个区间。

输出格式

仅包含一行,一个数,为最少花费。

题目解析

好像纯线性规划的题目都比较裸?

x_i为在第i号位置上建造的塔数。

于是可以写出线性规划:

\begin{equation} \min {w =\sum_{i=1}^{n} {C_{i} x_{i}}} \\ \left\{ \begin{aligned} \sum_{j=L_{i}}^{R_{i}} {x_{j}} & \ge D_{i} (1 \le i \le m) \\ x_{i} & \ge 0 (1 \le i \le n) \\ \end{aligned} \right. \nonumber \end{equation}

运用线性规划的对偶原理,可以这样化成标准形式(设S_{ij}为位置i是否被第j个区间所包含,1表示包含,0表示不包含):

\begin{equation} \max {z =\sum_{i=1}^{m} {D_{i} y_{i}}} \\ \left\{ \begin{aligned} \sum_{j=1}^{m} {S_{ij} {y_{j}}} & \le C_{i} (1 \le i \le n) \\ y_{i} & \ge 0 (1 \le i \le m) \\ \end{aligned} \right. \nonumber \end{equation}

为了描述得更清晰,给出样例的系数矩阵在对偶前后的情况:
2016030101

然后用单纯形解即可。另外了解了一下,发现这题里的矩阵是幺模矩阵,所以可以不用浮点数。顺便学习了一下幺模矩阵的判定

  • 幺模矩阵的判定的链接挂掉了。。。

    • 并不是挂掉了,是我还没写完……

  • anonymous

    ´ ▽ ` )ノHi 博主,想请教一个问题TAT
    是不是因为它是幺模的……所以过程中A矩阵一直是幺模的,然后,就能够保证a[l][e] > 0 ==> a[l][e] = 1这样呢TAT