【BZOJ1061】【Noi2008】—志愿者招募（线性规划+对偶）

传送门

---

Solution：

线性规划：

题目要求 ${Min}\sum_{i=1}^nC_ix_i$
满足约束
$\sum_{l_i\le j\le r_i}x_i\geq A_j,j\in[1,m]$
$x_i\geq0$

转对偶：

即求 ${Max}\sum_{j=1}^mA_jy_j$

满足约束 $\sum_{l_i\le j\le r_i}y_j\le C_i,i\in[1,n]$
$y_i\geq 0$

发现初始解可行，套板子就完了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return ib==ob?EOF:*ib++;
}
#define gc getchar
#define pb push_back
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
const int N=1005,M=10005;
int n,m;
double f[M][N];
const double eps=1e-6,inf=1e18;
inline void povit(int l,int e){
	double t=f[l][e];
	for(int j=0;j<=n;j++)f[l][j]/=t;
	for(int i=0;i<=m;i++)if(l!=i&&fabs(f[i][e])>0){
		t=f[i][e],f[i][e]=0;
		for(int j=0;j<=n;j++)f[i][j]-=t*f[l][j];
	}
}
inline void simplex(){
	while(1){
		int l=0,e=0;double mn=inf;
		for(int i=1;i<=n;i++)if(f[0][i]>eps){e=i;break;}
		if(!e)break;
		for(int i=1;i<=m;i++)if(f[i][e]>eps&&f[i][0]/f[i][e]<mn)
			mn=f[i][0]/f[i][e],l=i;
		povit(l,e);
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)f[0][i]=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();f[i][0]=read();
		for(int j=l;j<=r;j++)f[i][j]=1;
	}
	simplex();
	cout<<(int)-f[0][0];
}