# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 题解 P3337 【[ZJOI2013]防守战线】

posted on 2019-03-16 09:16:22 | under 题解 |

$$\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)$$

$$\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)$$

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 ;
}