题面自己上网查。
学了一下单纯形。当然 证明什么的 显然是没去学。不然估计就要残废了
上学期已经了解了 什么叫标准型。 听起来高大上 其实没什么
就是加入好多松弛变量+各种*(-1)，使得最后成为一般形式：
给定A[][]，求满足A[i][j]*Xj<=A[i][0];（0<i<=n,0<j<=m）
使A[0][j]*Xj最大的X[]；
如果题面中直接得出的条件是A[i][j]*Xj>=A[i][0]; 使 A[0][j]*Xj最小。
那么就要用对偶定理，变成 A[i][j]*Yi<=A[0][j] 使A[i][0]*Yi最大
（实际上只要把A转置一下就好了）
才写了两题单纯形，具体的怎么求Xi之类的 还没学，这里先放代码，之后再补
#include <bits/stdc++.h>
#define N 1005
#define M 10005
using namespace std;
const double eps=0.00000000001;
const double inf=;
double a[N][M]; int n,m,x,y;
void simplex(){
while (){
int x=,y=; double mn=inf,t;
for (int i=;i<=m;++i) if (a[][i]>eps) {y=i; break;} //找一个可以使答案增加的xi 只要系数为正就可以
if (!y) return; //没有了 说明答案已经不能再增加了
for (int i=;i<=n;++i) if (a[i][y]>eps&&a[i][]/a[i][y]<mn) mn=a[x=i][]/a[i][y]; //对找到的xi ,求出约束最紧的一条约束
if (!x) {a[][]=-inf; return;} //表示 可以无限增加
t=a[x][y]; a[x][y]=;
for (int i=;i<=m;++i) a[x][i]/=t;
for (int i=;i<=n;++i) if (i!=x&&abs(a[i][y])>eps){
t=a[i][y]; a[i][y]=; for (int j=;j<=m;++j) a[i][j]-=t*a[x][j];
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;++i) scanf("%lf",&a[i][]);
for (int i=;i<=m;++i){
scanf("%d%d%lf",&x,&y,&a[][i]);
for (int j=x;j<=y;++j) ++a[j][i];
}
simplex();
printf("%.0lf",round(-a[][]));
return ;
}
好短啊
18年来补。
UOJ的板子题。。应该比较科学了(忽略中间那个assert)
。还有就是 ，单纯形真的不靠谱，，还要random才能过？。。
#include <bits/stdc++.h>
#define DB long double
using namespace std;
const DB eps=0.000000001;
int n,m,T,k,t,o[],c[];
DB tmp[],a[][];
void SWAP(int k,int t){
swap(o[k],c[t]);
DB x=a[k][t]; a[k][t]=;
for (int j=;j<=n;++j) a[k][j]/=x;
for (int i=;i<=m;++i)
if (i!=k){
x=a[i][t]; a[i][t]=;
for (int j=;j<=n;++j) a[i][j]-=x*a[k][j];
}
}
int main(){
scanf("%d%d%d",&n,&m,&T);
for (int i=;i<=n;++i) scanf("%Lf",&tmp[i]);
for (int i=;i<=n;++i) c[i]=i;
for (int i=;i<=m;++i){
for (int j=;j<=n;++j) scanf("%Lf",&a[i][j]);
scanf("%Lf",&a[i][]); o[i]=i+n;
}
k=-;
for (int i=;i<=m;++i)
if (a[i][]<&&(k==-||a[i][]<a[k][])) k=i;
if (~k){
++n; c[n]=n+m;
for (int i=;i<=m;++i) a[i][n]=-;
SWAP(k,n);
while (){
t=-;
for (int j=n;j;--j)
if (a[][j]>eps) {t=j; if (rand()&) break;}
if (t==-) break;
k=-;
for (int i=;i<=m;++i)
if (a[i][t]>eps)
if (k==-||a[i][]/a[i][t]<a[k][]/a[k][t]) k=i;
SWAP(k,t);
}
if (fabs(a[][])>eps){
puts("Infeasible"); return ;
}
k=t=-;
for (int i=;i<=n;++i) if (c[i]==n+m) t=i;
for (int i=;i<=m;++i) if (o[i]==n+m) k=i;
if (~k){
for (int j=;j<=n;++j)
if (fabs(a[k][j])>eps) {t=j; break;}
if (t==-){
assert(); swap(o[k],o[m]);
for (int j=;j<=n;++j) swap(a[k][j],a[m][j]);
--m;
}else{
SWAP(k,t); swap(c[t],c[n]);
for (int i=;i<=m;++i) swap(a[i][t],a[i][n]);
--n;
}
}else{
swap(c[t],c[n]);
for (int i=;i<=m;++i) swap(a[i][t],a[i][n]);
--n;
}
}
for (int i=;i<=n;++i) a[][i]=;
for (int i=;i<=n;++i)
if (c[i]<=n) a[][i]+=tmp[c[i]];
for (int i=;i<=m;++i)
if (o[i]<=n)
for (int j=;j<=n;++j)
a[][j]-=tmp[o[i]]*a[i][j];
while (){
t=-;
for (int j=n;j;--j)
if (a[][j]>eps) {t=j; if (rand()&) break;}
if (t==-) break;
k=-;
for (int i=;i<=m;++i)
if (a[i][t]>eps)
if (k==-||a[i][]/a[i][t]<a[k][]/a[k][t]) k=i;
if (k==-){
puts("Unbounded");
return ;
}
SWAP(k,t);
}
printf("%.10Lf\n",-a[][]);
if (T){
for (int i=;i<=n;++i) tmp[c[i]]=;
for (int i=;i<=m;++i) tmp[o[i]]=a[i][];
for (int i=;i<=n;++i) printf("%.10Lf ",tmp[i]);
puts("");
}
return ;
}
天壌を翔る者たち