防守战线[ZJOI2013] & 志愿者招募[NOI2008]

$\rm{0x01}$ [ZJOI2013]防守阵线

传送门:https://www.luogu.org/problemnew/show/P3337

首先就是要明白怎么建模,大概就是:

$$
\text{最小化} \quad \sum c_ix_i \quad(i = 1,2,3\cdots n)\\\
\text{满足约束} \quad \sum \limits_{j=l_i}^{r_i} x_{j} \geq d_i \quad (i = 1,2,3\cdots m)
$$

其中$x_j$表示$j$这个地方有几座塔。

那我们首先把它对偶过去,就会得到:
$$
\text{最大化} \quad \sum d_iy_i \quad(i = 1, 2,3 \cdots m) \\\
\text{满足约束} \quad \sum \limits_{j=l_i}^{r_i} y_{j} \leq c_i\quad (i = 1,2,3\cdots n)
$$
然后我们考虑,似乎价值不能带小数啊,毕竟题目中规定了价值都为整数(事实上并没有规定但是数据是这样给的),换句话说我们不能存在建某座塔的一部分(比如只建一半)。

那么这就是整数线性规划问题,换句话说就是自变量取值范围是$\Z$的线性规划

呃,这问题已经被证明是$\rm{NP-Hard}$的问题了…但是,有一种矩阵叫做全幺模矩阵,即元素只会是$\boldsymbol{0,1,-1}$的矩阵,被证明肯定至少有一组最优解保证整数线性规划与实数线性规划的方案一致。

啥,你说啥?你要关于全幺模矩阵这个性质的争鸣?是百家争鸣那个争鸣吗?学OI呢别瞎讨论历史

然后就可以一发单纯形给艹过去啦~开心心~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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) ;
}
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 ;
}

怎么说呢,似乎单纯形有好多地方的写法都比较灵活让我不知道背什么样的板子会更好

$\rm{0x02}$ [NOI2008] 志愿者招募

传送门:https://www.luogu.org/problemnew/show/P3980

什么鬼啊这不是上面的那道题吗

还是:
$$
\text{最小化} \quad \sum c_ix_i \quad(i = 1,2,3\cdots m)\\\
\text{满足约束} \quad \sum \limits_{j=1}^{m} w_{i,j}x_{j} \geq A_i \quad (i = 1,2,3\cdots n)
$$
其中$x_j$表示选择的第$j$类志愿者的个数,$w_{i,j}$表示在第$i$天,第$j$类志愿者能否选择。那么还是老样子,对偶过去就可以得到:
$$
\text{最大化} \quad \sum A_ix_i \quad(i = 1,2,3\cdots n)\\\
\text{满足约束} \quad \sum \limits_{j=1}^{m} w_{i,j}x_{j} \leq c_i \quad (i = 1,2,3\cdots m)
$$
怎么说呢……这个一开始的建模比上一个题还是有难度的,因为上一个题的$L_i,R_i$跟约束有关,而这次的$L_i,R_i$则是跟目标函数有关——或许不应该这么说,但是看上去确实不如上面那题跟约束有关系就对了(我在BB一堆什么啊)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cmath> 
#include <cstdio>
#include <iostream>

#define INF 1e9
#define MAXN 1035
#define MAXM 10010

const double eps = 1e-8 ; double res ;
using namespace std ; int b[MAXM], e[MAXM] ;
int N, M, i, j, k ; double C[MAXM], _need[MAXM], A[MAXM][MAXN] ;

inline void Pivot(int posN, int posC){
C[posC] /= A[posC][posN] ; // constraint divided by A_{l,e}
for (int p = 1 ; p <= N ; ++ p) if (p != posN) A[posC][p] /= A[posC][posN] ;//this line Booom
A[posC][posN] = 1 ;
// Pivot is above, taking it back is below
for (int p = 1 ; p <= M ; ++ p)//taking back to constraints
if (p != posC && fabs(A[p][posN]) > eps){
C[p] -= A[p][posN] * C[posC] ;
for (i = 1 ; i <= N ; ++ i)
if (i != posN) A[p][i] -= A[p][posN] * A[posC][i] ;
A[p][posN] = 0 ;
}
res += _need[posN] * C[posC] ;//this time results in a better INIT-Sol
for (int p = 1 ; p <= N ; ++ p) if (p != posN) _need[p] -= _need[posN] * A[posC][p] ;
_need[posN] = - _need[posN] * A[posC][posN] ;
}

inline double simplex(){
while(1){
j = 0, k = 0 ; double MAX = INF ;
for (j = 1 ; j <= N ; ++ j) if (_need[j] > eps) break ; /*1*/ if (j > N) return res ; //make-it-sure if go on
for (i = 1 ; i <= M ; ++ i) if (A[i][j] > eps && MAX > C[i] / A[i][j]) MAX = C[i] / A[i][j], k = i ; //find the min_val constraint
if (MAX >= INF) return INF ; /* this task is unbounded */ Pivot(j, k) ;
}
}
int main(){
cin >> N >> M ;
for (i = 1 ; i <= N ; ++ i) cin >> _need[i] ;
for (i = 1 ; i <= M ; ++ i){
scanf("%d%d%lf", &b[i], &e[i], &C[i]) ;
for (j = b[i] ; j <= e[i] ; ++ j) A[i][j] = 1 ;
}
printf("%d\n", (int)(simplex()+0.5)) ; return 0 ;
}

$\rm{Reference}$