题目大意
本题中你需要求解一个标准型线性规划：
有$n$个实数变量$x_1,x_2,\ldots,x_n$和$m$条约束，其中第$i$条约束形如$\sum_{j=1}^na_{ij}x_j\le b_i$。
此外这$n$个变量需要满足非负性限制，即$x_j\ge0$。
在满足上述所有条件的情况下，你需要指定每个变量$x_j$的取值，使得目标函数$F=\sum_{j=1}^nc_jx_j$的值最大。
题目分析
假·单纯形模板题。
首先这道题我们并不知道 非基本变量全为$0$ 的初始解是否合法，故需要手动寻找初始解。（学习笔记）
显然，我们可以使用随机化！
不！！我们使用随机化被卡了！
所有使用随机化的都被卡了，不是初始化死循环，就是初始化卡精度，就是初始化判错无解。（坑啊，Extra的所有点都是用来卡随机化的）
为了拒绝初始化，$97$分就$97$分！
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=105,maxm=105;
const double eps=1e-8;
int t,id[maxn+maxm];
double ans[maxn+maxm];
int dcmp(double x) {
if(fabs(x)<=eps)return 0;
return x>eps?1:-1;
}
struct Simplex {
int n,m;
double a[maxn][maxm];
void init(int m,int n) {
this->n=m;
this->m=n;
}
bool find() {
while(true) {
int in=0,out=0;
for(int i=1; i<=n; i++)
if(dcmp(a[i][0])<0&&(!out||(rand()&1)))out=i;
if(!out)break;
for(int j=1; j<=m; j++)
if(dcmp(a[out][j])>0&&(!in||(rand()&1)))in=j;
if(!in)return false;
pivot(in,out);
}
return true;
}
void pivot(int in,int out) {
swap(id[m+out],id[in]);
for(int i=0; i<=m; i++)
if(i!=in)a[out][i]/=-a[out][in];
a[out][in]=1/a[out][in];
for(int i=0; i<=n; i++) {
if(i==out||dcmp(a[i][in])==0)continue;
double t=a[i][in];
a[i][in]=0;
for(int j=0; j<=m; j++)a[i][j]+=t*a[out][j];
}
}
void Solve() {
while(true) {
int in=0,out=0;
double Min=1e18;
for(int i=1; i<=m; i++)
if(dcmp(a[0][i])>0) {
in=i;
break;
}
if(!in)break;
for(int i=1; i<=n; i++)
if(dcmp(a[i][in])<0&&a[i][0]/-a[i][in]<Min) {
Min=a[i][0]/-a[i][in];
out=i;
}
if(!out) {
puts("Unbounded");
return;
}
pivot(in,out);
}
printf("%0.8lf\n",a[0][0]);
if(t) {
for(int i=1; i<=n; i++)ans[id[m+i]]=a[i][0];
for(int i=1; i<=m; i++)printf("%0.8lf ",ans[i]);
}
}
} fst;
int n,m;
int main() {
srand(99995999);
n=Get_Int();
m=Get_Int();
t=Get_Int();
fst.init(m,n);
for(int i=1; i<=n; i++)fst.a[0][i]=Get_Int();
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++)
fst.a[i][j]=-Get_Int();
fst.a[i][0]=Get_Int();
}
for(int i=1; i<=n; i++)id[i]=i;
if(!fst.find())puts("Infeasible");
else fst.Solve();
return 0;
}
|
