P3980

· · 题解

设第 i 天需要 x_i 个志愿者，记 m_{ij} 表示第 i 天第 j 个志愿者是否能工作，则它们需要满足如下条件：

于是所需费用即 C_1 x_1 + C_2 x_2 + \cdots + C_m x_m，需要令它最小化。

可以看出，这是一个线性规划问题。

由于它是最小化型线性规划，不是标准形式的。因此，可以利用线性规划对偶定理 (证明可以百度等，比如这里) 将其转化为一个最大化型线性规划：

由于 C_i 都是 \geq 0 的整数，于是上面的线性规划就有基本解 (零解)。于是写个最单纯的单纯形法就可以了 (连 init() 都不用写~)。

具体地过程，就是寻找大于 0 的非基 (自由) 变量转化成基变量，然后转轴 (注意代码实现时和 Gauss 消元的区别)，最后得到的就是最小花费。

(其实现在还有一个问题，就是线性规划的最优解会不会出现分数的问题，这个放到最后讲)。

代码：

#include <bits/stdc++.h>
#define N 1034
#define E 10034
using namespace std;

const double eps = 1e-8;

int n, e, l, r;
int i, j;

int id[N + E];
double m[E][N], b[E], *c = m[0], ans[N + E];

void pivot(int r, int c){
    int i, j; double coe = 1.0 / m[r][c];
    swap(id[n + r], id[c]);
    m[r][c] = 1.0;
    for(j = 1; j <= n; ++j)
        m[r][j] *= coe;
    b[r] *= coe;
    for(i = 0; i <= e; ++i){
        if(i == r) continue;
        coe = m[i][c]; m[i][c] = 0.0;
        for(j = 1; j <= n; ++j)
            m[i][j] -= coe * m[r][j];
        b[i] -= coe * b[r];
    }
}

bool simplex(){
    int i, j, basic, free; double G;
    for(; ; ){
        basic = free = 0; G = INFINITY;
        for(i = 1; i <= n; ++i) // free (nonbasic) variable
            if(c[i] > c[free]) free = i;
        if(!free) return true;
        for(j = 1; j <= e; ++j) // basic variable
            if(m[j][free] > eps && b[j] < G * m[j][free]){
                G = b[j] / m[j][free]; basic = j;
            }
        if(!basic) return puts("Unbounded"), false;
        pivot(basic, free);
    }
}

int main(){
    scanf("%d%d", &n, &e);
    for(j = 1; j <= n; ++j) scanf("%lf", c + j);
    for(i = 1; i <= e; ++i){
        scanf("%d%d%lf", &l, &r, b + i);
        for(j = l; j <= r; ++j)
            m[i][j] = 1.0;
    }
    if(simplex())
        printf("%.lf\n", -*b);
    return 0;
}

(听说这题还可以用最小费用最大流做？等待楼上来填坑)

接下来一个小细节就是证明上述线性规划必有整数解。

我们知道，线性规划的问题的最优解为整数的一个必要条件是它的任意一个子方阵的行列式为 -1, 0, 1。

而这是一个 0/1 方阵，且每一行中的 1 是连续的。我们接下来证明，这个方阵的行列式一定为 -1, 0, 1 中之一。

我们先用第 n-1 列乘上 -1 加到第 n 列，第 n-2 列乘上 -1 加到第 n-1 列，……，第 1 列乘上 -1 加到第 2 列，就得到了一个新方阵：

其中每一行有左边一个 1，右边 1 个 -1 (也可能没有)，比如：

 1  0  0 -1  0  0  0
 1  0  0  0  0 -1  0
 0  1  0  0 -1  0  0
 0  1  0  0  0  0 -1
 0  0  1  0  0 -1  0
 0  0  0  1  0  0  0
 0  0  0  0  1 -1  0

我们将这些行按照 1 的位置从左到右排序，相同的以 -1 为第二关键字排序，如上面的矩阵 (已经排好序的)，可知它的行列式要么不变，要么变为它的相反数。

接下来，对于 1 的位置相同的几行，把最上面一行乘以 -1，加到下面几行 (就像 Gauss 消元一样)，最后再排序，重复此过程，会得到 (类似) 如下的矩阵：

 1  0  0 -1  0  0  0
 0  1  0  0 -1  0  0
 0  0  1  0  0 -1  0
 0  0  0  1  0 -1  0
 0  0  0  0  1 -1  0
 0  0  0  0  0  1 -1
 0  0  0  0  0  0  1

最终情况下，它要么是一个上三角矩阵，则原行列式显然为 \pm 1，当然，像 Gauss 消元一样，可能出现中间某个时刻一行为 0，那么原行列式就为 0，证毕。