线性规划


高斯消元思想

矩阵初等变换

线性规划

P3980 NOI2008 志愿者招募

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

那么最后需要的费用:

题目要我们使它最小。

  • 线性规划对偶定理:

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

变换后:

我们要使

最大。

这里我们用矩阵来处理,和高斯消元有些相似,把目标(人数要求)处理完了,目标的权值相反数即使结果(开始的时候权值为 $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;
}

文章作者: 王大神——A001
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 王大神——A001 !
  目录