ZJOI2013 防守战线

题目

战线可以看作一个长度为\(n\)的序列，现在需要在这个序列上建塔来防守敌兵，在序列第\(i\)号位置上建一座塔有\(C_i\)的花费，且一个位置可以建任意多的塔，费用累加计算。有\(m\)个区间\([L_1,R_1],[L_2,R_2],…,[L_m,R_m]\)，在第\(i\)个区间的范围内要建至少\(D_i\)座塔。求最少花费。

算法1——费用流

我们会发现这题很像Noi2008 志愿者招募。

但是两式相减之后却不能产生想[志愿者招募]一样的效果，原因是对于一个区间，它体现在矩阵里面的系数不是在同一列，而是在同一行。

有个神奇的东西，就是转换成这个问题的对偶问题。对偶问题怎么转换呢，链接。

我觉得这个“证明”好形象！

然后我们就可以像[志愿者招募]一样构图，接着用跑费用流了，但是最“原始”的费用流会被卡掉\(3\)个点，所以我们要用\(zkw\)网络流！

一开始我有点担心图中会不会出现正圈，lzh教导我：如果原图没有正圈，那么残余网络中也不会有正圈！

算法2——单纯形

这个单纯形，我弄了一整个早上才明白。

这里是维基的资料。

关于单纯形，什么时候我们能跑整数的呢（在这题里面，矩阵里的元素只有\(-1,0,1\)）？想到省赛就要来了，先把这个问题放一放。贴吧里有个帖子就是讨论这个的。

贴个代码，虽然不需要用double，但我还是先写个标准的单纯形吧。

#include <cstdio>

#include <cmath>

#include <iostream>

#include <assert.h>

using namespace std;

const int MAXN = 1003;

const int MAXM = 10003;

const double INF = 1e100;

const double EPS = 1e-8;

int n, m;

double A[MAXN][MAXM];

int main() {

	freopen("defend.in", "r", stdin);

	freopen("defend.out", "w", stdout);

	scanf("%d%d", &n, &m);

	n ++, m ++;

	for (int i = 1; i < n; i ++) {

		scanf("%lf", A[i] + m);

	}

	for (int i = 1; i < m; i ++) {

		int L, R;

		scanf("%d%d%lf", &L, &R, A[n] + i);

		for (int j = L; j <= R; j ++)

			A[j][i] = 1;

	}

	while (true) {

		int x = -1, y;

		for (int i = 1; i < m; i ++) {

			if (A[n][i] - EPS <= 0) continue;

			x = i;

			y = -1;

			double tval = INF;

			for (int j = 1; j < n; j ++) {

				if (A[j][i] - EPS <= 0) continue;

				double tmp = A[j][m] / A[j][i];

				if (tmp < tval) {

					tval = tmp;

					y = j;

				}

			}

			assert(y != -1);

			break;

		}

		if (x == -1) break;

		for (int i = 1; i <= m; i ++)

			if (i != x) A[y][i] /= A[y][x];

		A[y][x] = (double) 1 / A[y][x];

		for (int i = 1; i <= n; i ++)

			if (fabs(A[i][x]) > EPS)

				for (int j = 1; j <= m; j ++)

					if (i != y && j != x)

						A[i][j] -= A[i][x] * A[y][j];

		for (int i = 1; i <= n; i ++)

			if (i != y) A[i][x] *= - A[y][x];

	}

	printf("%.0lf\n", (double) - A[n][m]);

	return 0;

}