这是一道模板题。
本题中你需要求解一个标准型线性规划：
有nn个实数变量x1,x2,⋯,xnx1,x2,⋯,xn和mm条约束，其中第ii条约束形如∑nj=1aijxj≤bi∑j=1naijxj≤bi。
此外这nn个变量需要满足非负性限制，即xj≥0xj≥0。
在满足上述所有条件的情况下，你需要指定每个变量xjxj的取值，使得目标函数F=∑nj=1cjxjF=∑j=1ncjxj的值最大。
输入格式
第一行三个正整数 n,m,tn,m,t。其中t∈{0,1}t∈{0,1}。
第二行有nn个整数c1,c2,⋯,cnc1,c2,⋯,cn，整数间均用一个空格分隔。
接下来mm行，每行代表一条约束，其中第ii行有n+1n+1个整数ai1,ai2,⋯,ain,biai1,ai2,⋯,ain,bi，整数间均用一个空格分隔。
输出格式
如果不存在满足所有约束的解，仅输出一行"Infeasible"。
如果对于任意的MM，都存在一组解使得目标函数的值大于MM，仅输出一行"Unbounded"。
否则，第一行输出一个实数，表示目标函数的最大值FF。当第一行与标准答案的相对误差或绝对误差不超过10−610−6，你的答案被判为正确。
如果t=1t=1，那么你还需要输出第二行，用空格隔开的nn个非负实数，表示此时x1,x2,⋯,xnx1,x2,⋯,xn的取值，如有多组方案请任意输出其中一个。
判断第二行是否合法时，我们首先检验F−∑nj=1cjxjF−∑j=1ncjxj是否为00，再对于所有ii，检验min{0,bi−∑nj=1aijxj}min{0,bi−∑j=1naijxj}是否为00。检验时我们会将其中大于00的项和不大于00的项的绝对值分别相加得到S+S+和S−S−，如果S+S+和S−S−的相对误差或绝对误差不超过10−610−6，则判为正确。
如果t=0t=0，或者出现Infeasible或Unbounded时，不需要输出第二行。
样例一
input
2 2 1 1 1 2 1 6 -1 2 3
output
4.2 1.8 2.4
explanation
两条约束分别为2x1+x2≤6,−x1+2x2≤32x1+x2≤6,−x1+2x2≤3。
当x1=1.8,x2=2.4x1=1.8,x2=2.4时目标函数x1+x2x1+x2取到最大值4.24.2。
样例二
input
2 2 1 1 -1 1 1 4 -1 -2 -2
output
4.0 4.0 0.0
explanation
注意xj≥0xj≥0的限制。
样例三
input
3 3 1 0 0 1 -2 1 0 -4 1 1 0 4 1 -2 0 -4
output
Infeasible
样例四
input
2 1 1 0 1 1 0 1
output
Unbounded
限制与约定
对于所有数据，1≤n,m≤201≤n,m≤20，0≤|aij|,|bi|,|cj|≤1000≤|aij|,|bi|,|cj|≤100，t∈{0,1}t∈{0,1}。
本题包含4个子任务，每个25分。
子任务1,3满足bi≥0bi≥0。
子任务2,4没有特殊限制。
子任务1,2中t=0t=0。
子任务3,4中t=1t=1。
时间限制：1s1s
空间限制：256MB
正解：线性规划模板。
看了各种博客论文，现在还不是很理解。
板子参见xlightgod学长，话说完全蒯代码真的好吗。。然而我把ctime和srand去掉了才AC。。
学长的两篇博客：
http://blog.xlightgod.com/%E3%80%90uoj179%E3%80%91%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/
http://blog.xlightgod.com/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92%E4%B8%8E%E5%8D%95%E7%BA%AF%E5%BD%A2%E6%B3%95/
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define eps (1e-12) 15 #define inf (1e15) 16 #define il inline 17 #define RG register 18 #define double long double 19 20 using namespace std; 21 22 double a[50][50],val[50],ans; 23 int L[50],E[50],b[50],n,m; 24 25 il int gi(){ 26 RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); 27 if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; 28 } 29 30 il void pivot(RG int l,RG int e){ 31 swap(L[l],E[e]); RG double k=a[l][e]; a[l][e]=1; 32 for (RG int i=0;i<=n;++i) a[l][i]/=k; RG int len=0; 33 for (RG int i=0;i<=n;++i) if (fabs(a[l][i])>eps) b[++len]=i; 34 for (RG int i=0;i<=m;++i) 35 if (i!=l && fabs(a[i][e])>eps){ 36 k=a[i][e],a[i][e]=0; 37 for (RG int j=1;j<=len;++j) a[i][b[j]]-=k*a[l][b[j]]; 38 } 39 return; 40 } 41 42 il double simplex(){ 43 while (1){ 44 RG int l,e; for (e=1;e<=n;++e) if (a[0][e]>eps) break; 45 if (e==n+1) return -a[0][0]; RG double tmp=inf; 46 for (RG int i=1;i<=m;++i) 47 if (a[i][e]>eps && a[i][0]/a[i][e]<tmp) tmp=a[i][0]/a[i][e],l=i; 48 if (tmp==inf) return inf; pivot(l,e); 49 } 50 } 51 52 il int init(){ 53 for (RG int i=1;i<=n;++i) E[i]=i; 54 while (1){ 55 RG int l=0,e=0; 56 for (RG int i=1;i<=m;++i) if (a[i][0]<-eps && (!l || (rand()&1))) l=i; if (!l) return 1; 57 for (RG int i=1;i<=n;++i) if (a[l][i]<-eps && (!e || (rand()&1))) e=i; if (!e) return 0; 58 pivot(l,e); 59 } 60 } 61 62 il void work(){ 63 n=gi(),m=gi(); RG int t=gi(); 64 for (RG int i=1;i<=n;++i) scanf("%Lf",&a[0][i]); 65 for (RG int i=1;i<=m;++i){ 66 for (RG int j=1;j<=n;++j) scanf("%Lf",&a[i][j]); 67 scanf("%Lf",&a[i][0]); 68 } 69 if (!init()){ puts("Infeasible"); return; } ans=simplex(); 70 if (ans==inf) puts("Unbounded"); else{ 71 printf("%0.8Lf ",ans); if (!t) return; 72 for (RG int i=1;i<=m;++i) val[L[i]]=a[i][0]; 73 for (RG int i=1;i<=n;++i) printf("%0.8Lf ",val[i]); 74 } 75 return; 76 } 77 78 int main(){ 79 work(); 80 return 0; 81 }