题解 P3337 【[ZJOI2013]防守战线】
皎月半洒花
2019-03-16 09:16:22
一道……呃……比较水的线性规划？~~完全就是跟某“志愿者招募”一毛一样的题~~
我们先抽象出数学模型来：
$$\text{最小化\quad} \sum c_ix_i \quad(i = 1,2,3\cdots n)$$
$$\text{满足约束\quad} \sum \limits_{j=l_i}^{r_i} x_{i,j} \geq d_i \quad (i = 1,2,3\cdots m)$$
其中$x_i$表示在$i$处有几座塔。
这玩意儿并不可以直接上线性规划，应该先对偶过去。而因为本题的约束矩阵是**全幺模矩阵**，即**每个元素只会是$\bold{0,1,-1}$的矩阵**，所以至少有一组最优解保证整数线性规划与实数线性规划的方案一致。
那么我们对偶过来就是
$$\text{最大化\quad} \sum d_ix_i \quad(i = 1, 2,3 \cdots m)$$
$$\text{满足约束\quad} \sum \limits_{j=l_i}^{r_i} x_{i,j} \leq c_i\quad (i = 1,2,3\cdots n)$$
然后就可以一发单纯性爆艹过去了……
话说似乎现在单纯性算法在OI中几乎绝迹了，只能用来配合网络流骗分……
真可怕啊qaq
```cpp
const double eps = 1e-8, INF = 1e9 ;
using namespace std ; double A[MAXN][MAXM] ;
int N, M, B, E, i, j, k, p ; double res, t, cost[MAXM], _need[MAXM] ;
inline void Pivot(int e, int l){
cost[l] /= A[l][e], t = A[l][e], A[l][e] = 1;
for (i = 1 ; i <= M ; ++ i) if (i != e) A[l][i] /= t ;
for (i = 1 ; i <= N ; ++ i)
if (i != l && abs(A[i][e]) > eps){
cost[i] -= A[i][e] * cost[l] ;
for (p = 1 ; p <= M ; ++ p) if (p != e) A[i][p] -= A[i][e] * A[l][p] ;
A[i][e] = - A[i][e] * A[l][e] ;
}
res += _need[e] * cost[l] ;
for (i = 1 ; i <= M ; ++ i) if (i != e) _need[i] -= _need[e] * A[l][i] ;
_need[e] = - _need[e] * A[l][e] ;
}
double simplex(){
while (true){
double MINX = INF ; j = 0, k = 0 ;
for (j = 1 ; j <= M ; ++ j) if (_need[j] > eps) break ; if (j > M) return res ;
for (i = 1 ; i <= N ; ++ i) if (A[i][j] > eps && MINX > cost[i] / A[i][j]) k = i, MINX = cost[i] / A[i][j] ;
if (MINX >= INF) return INF ; Pivot(j, k) ;
}
return res ;
}
int main(){
cin >> N >> M ;
for (i = 1 ; i <= N ; ++ i) scanf("%lf", &cost[i]) ;
for (i = 1 ; i <= M ; ++ i){
scanf("%d%d%lf", &B, &E, &_need[i]) ; //约束
for (j = B ; j <= E ; ++ j) A[j][i] = 1.0 ;
}
printf("%d\n", (int)(simplex() + 0.5)) ; return 0 ;
}
```