前言
想学好久了，这几天终于看懂了，来写一发。
线性规划
线性规划是指具有以下形式的问题：
[max{sum_{i=1}^{n}x_ia_i}\
left{egin{array}{l}
forall i,sum_{j=1} a_{i,j}x_i=b_i\
forall i,x_ige 0
end{array}
ight.]
不过对于 (le) 的形式，我们可以通过松弛变量来实现，具体来说就是：
[max{sum_{i=1}^{n}x_ia_i}\
left{egin{array}{l}
a_{n+i}=b_i-sum_{j=1} a_{i,j}x_i\
forall i,x_ige 0
end{array}
ight.
]
线性规划-单纯形
总所周知，高中的线性规划解法就是找到可行域，然后用函数逼近找最值。（似乎表述的有些不严谨
然后在OI中，似乎是可以说明这个可行域是个多维凸包，就可以用爬山算法直接爆凸(艹皿艹 )，单纯性算法就是这个算法的具体实现。
我们定义一种操作叫做转轴，举个例子：
假如我们现在的问题是求解以下问题：
[max {3x_1+x_2+2x_3}\
left{egin{array}{l}
x_4=30-x_1-x_2-3_x3\
x_5=24-2x_1-2x_2-5x_3\
x_6=36-4x_1-x_2-2x_3\
forall x_i,x_ige 0
end{array}
ight.
]
我们把 (x_1) 用其他值来替换，我们发现限制最紧的是 (x_6)，于是我们把 (x_1) 用 (x_2,x_3,x_6) 替换，可以得到：
[max{27+frac{x_2}{4}+frac{x_3}{2}-frac{3x_6}{4}}\
left{egin{array}{l}
x_4=21-frac{3x_2}{4}-frac{5x_3}{2}+frac{x_6}{4}\
x_5=6-frac{3x_2}{2}-4x_3+frac{x_6}{2}\
x_1=9-frac{x_2}{4}-frac{x_3}{2}-frac{x_6}{4}\
forall x_i,x_ige 0
end{array}
ight.
]
不难发现，我们再依次转轴 (x_3,x_2) 可以得到：
[max{28-frac{x_3}{6}-frac{x_5}{6}-frac{2x_6}{3}}\
left{egin{array}{l}
x_4=18-frac{x_3}{2}+frac{x_5}{2}\
x_2=4-frac{8x_3}{3}-frac{2x_5}{3}+frac{x_6}{3}\
x_1=8+frac{x_3}{6}+frac{x_5}{6}-frac{x_6}{3}\
forall x_i,x_ige 0
end{array}
ight.
]
你可以发现的是，这个时候需要最大化的式子里面所有系数都是负数，也就是说，答案最大不可能比这更大了，这个时候只需要取 (x_3,x_5,x_6) 都取 (0) 即可。
不过我们可以发现的是，如果我们如果一开始的 (b_i<0) 的话，我们这样取值是不可以的。但是我们可以直接通过转轴把它转正即可。 举个例子。
[x_1=-4+x_2-x_3
]
我们可以通过转轴得到：
[x_2=4+x_1+x_3
]
这样就可以了。
不过转轴操作由于你一直转第一次发现的东西可能会卡入死循环，所以你随机取点就可以了。
时间复杂度玄学，虽然是指数级的，但是你可以发现指数级的情况需要值域很大，所以在值域正常的情况下，还是跑地很快的。
但是我们可以发现要达到这个指数级的调用次数，边权也必须是指数级的。所以在OI中往往跑得比谁都快。所以“能在1s内跑出范围为几百的数据”。 --- 神犇zzq
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define inf 0x7f7f7f7f
#define eps 1e-7
#define MAXN 55
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,t,ind[MAXN];
double a[MAXN][MAXN],ans[MAXN];
int dcmp (double x){
if (x > eps) return 1;
if (x < -eps) return -1;
return 0;
}
void pivot (int r,int c){
swap (ind[r + n],ind[c]);
double x = -a[r][c];a[r][c] = -1;
for (Int i = 0;i <= n;++ i) a[r][i] /= x;
for (Int i = 0;i <= m;++ i) if (dcmp (a[i][c]) && i != r){
x = a[i][c],a[i][c] = 0;
for (Int j = 0;j <= n;++ j) a[i][j] += a[r][j] * x;
}
}
void solve (){
for (Int i = 1;i <= n;++ i) ind[i] = i;
while (1){
int x = 0,y = 0;
for (Int i = 1;i <= m;++ i) if (dcmp (a[i][0]) < 0 && (!x || rand() & 1)) x = i;
if (!x) break;//可以直接开始单纯形算法了
for (Int i = 1;i <= n;++ i) if (dcmp (a[x][i]) > 0 && (!y || rand() & 1)){y = i;break;}
if (!y) return puts ("Infeasible"),void ();
pivot (x,y);
}
while (1){
int x = 0,y = 0;
for (Int i = 1;i <= n;++ i) if (dcmp (a[0][i]) > 0 && (!x || rand() & 1)) x = i;
if (!x) break;//所有基变量系数都为负数了
double w,t;bool f = 1;
for (Int i = 1;i <= m;++ i) if (dcmp (a[i][x]) < 0 && (t = a[i][0] / -a[i][x],f || t < w)) f = 0,w = t,y = i;
if (!y) return puts ("Unbounded"),void ();
pivot (y,x);
}
printf ("%.9f
",a[0][0]);
if (!t) return ;
for (Int i = n + 1;i <= n + m;++ i) ans[ind[i]] = a[i - n][0];
for (Int i = 1;i <= n;++ i) printf ("%.9f ",ans[i]);putchar ('
');
}
signed main(){
read (n,m,t);
for (Int i = 1;i <= n;++ i) scanf ("%lf",&a[0][i]);
for (Int i = 1;i <= m;++ i){
for (Int j = 1;j <= n;++ j) scanf ("%lf",&a[i][j]),a[i][j] = -a[i][j];
scanf ("%lf",&a[i][0]);
}
solve ();
return 0;
}