线性规划

高斯消元思想

矩阵初等变换

线性规划

P3980 NOI2008 志愿者招募

$b_{ij}$ 判断第 $i$ 天第 $j$ 个志愿者是否可以工作（是否在他的干活时间）。$x_i$ 每种志愿者的数量。

$$b_{11}x_1+b_{12}x_2+…+b_{1m}x_m\ge a_1$$ $$b_{21}x_1+b_{22}x_2+…+b_{2m}x_m\ge a_2$$ $$b_{31}x_1+b_{32}x_2+…+b_{3m}x_m\ge a_3$$ $$\vdots$$ $$b_{n1}x_1+b_{n2}x_2+…+b_{nm}x_m\ge a_n$$ $$x_1,x_2,…,x_m\ge 0$$

那么最后需要的费用：

$$\sum_{i=1}^m{c_ix_i}$$

题目要我们使它最小。

• 线性规划对偶定理：

简单来说就是换了一种表达方式，但是意义不变。例如：$5 > 3$ 和 $3 < 5$ 是一个意思，只是位置不同了。

变换后：

$$b_{11}y_1+b_{12}y_2+…+b_{1m}y_n\le c_1$$ $$b_{21}y_1+b_{22}y_2+…+b_{2m}y_n\le c_2$$ $$b_{31}y_1+b_{32}y_2+…+b_{3m}y_n\le c_3$$ $$\vdots$$ $$b_{n1}y_1+b_{n2}y_2+…+b_{nm}y_n\le c_m$$ $$y_1,y_2,…,y_n\ge 0$$

我们要使

$$\sum_{i=1}^n{a_iy_i}$$

最大。

这里我们用矩阵来处理，和高斯消元有些相似，把目标（人数要求）处理完了，目标的权值相反数即使结果（开始的时候权值为 $0$），但不完全一样，同时可以借鉴初等变换的内容。

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
using namespace std;
long long r_r(){//快读
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar(); 
  }
  return x*f;
}
const double m_i=1e-8;
const int m_a=1e9+10;
const int o_o=1e3+10;
int n,m;
double v_i[o_o<<4][o_o];//记录每种志愿者在每天干活的贡献 
double b_b[o_o<<4];//每种志愿者的费用 
void u_p(int k,int x){//消元 
  double c_i=1.0/v_i[k][x];//将当前位置化为 1 的值 
    for(int i=1;i<=n;i++)v_i[k][i]*=c_i;//更新行 
    b_b[k]*=c_i;//更新花费 
    for(int i=0;i<=m;i++){
        if(i==k)continue;//是当前行 
        c_i=v_i[i][x];//记录当前的价值 
    v_i[i][x]=0.0;//清空 
        for(int j=1;j<=n;j++)
            v_i[i][j]-=c_i*v_i[k][j];//更新贡献 
        b_b[i]-=c_i*b_b[k];//更新花费 
    }
}
void f_i(){
    while(1){
        int k_i=0;//更新的志愿者的种类 
    int x_i=0;//更新的是哪天 
    double k_k=m_a;
        for(int i=1;i<=n;i++)//记录每项工作中还需要的人数最多的任务 
            if(v_i[0][i]>v_i[0][x_i])x_i=i;
        if(!x_i)return ;//全部满足要求 
        
        //找到最小满足要求人数的志愿者类型 
        for(int i=1;i<=m;i++)//尝试每种志愿者 
            if(v_i[i][x_i]>m_i&&b_b[i]<k_k*v_i[i][x_i]){//最小花费 
                k_k=b_b[i]/v_i[i][x_i];//更新花费 
        k_i=i;//记录雇的是哪种志愿者 
            }
        u_p(k_i,x_i);//更新 
    }
}
int main(){
  n=r_r(),m=r_r();
    for(int i=1;i<=n;i++)scanf("%lf",&v_i[0][i]);
    for(int i=1;i<=m;i++){//每种志愿者的工作时间和报酬 
      int l=r_r(),r=r_r();
    scanf("%lf",&b_b[i]);//记录价格 
        for(int j=l;j<=r;j++)v_i[i][j]=1.0;//区间标记能工作 
    }
    f_i();
  printf("%.lf\n",-b_b[0]);//输出价值 
    return 0;
}