单纯形裸题….话说单纯形好像只有裸题。 b数组为基变量，c数组为非基变量。当所有非基变量系数小于0时，我们令所有的非基变量等于0最优解及后面的常数。
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; const int maxn=100010; const double inf = 1000000000000.00; int n,m,x,y,z; double a[10100][1010],b[10100],c[1010],v; double eps=1e-7; inline void pivot(int l,int e){ int i,j; b[l]/=a[l][e]; for(i=1;i<=n;i++) if(i!=e) a[l][i]/=a[l][e]; a[l][e]=1/a[l][e]; for(i=1;i<=m;i++)if(i!=l&&fabs(a[i][e])>eps){ b[i]-=a[i][e]*b[l]; for(j=1;j<=n;j++) if(j!=e)a[i][j]-=a[i][e]*a[l][j]; a[i][e]=-a[i][e]*a[l][e]; } v+=c[e]*b[l]; for(i=1;i<=n;i++)if(i!=e)c[i]-=c[e]*a[l][i]; c[e]=-c[e]*a[l][e]; } double Simplex() { int i,l,e; while(1) { for(i=1;i<=n;i++) if(c[i]>eps) break; if((e=i)==n+1) return v; double temp=inf; for(i=1;i<=m;i++) if(a[i][e]>eps&&b[i]/a[i][e]<temp) temp=b[i]/a[i][e],l=i; if(temp==inf) return inf; pivot(l,e); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lf",&c[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); for(int j=x;j<=y;j++) { a[i][j]=1; } scanf("%lf",&b[i]); } double ans=Simplex(); printf("%d\n",int(ans+0.5)); return 0; }