【UOJ179】线性规划

【题目链接】

• 点击打开链接
  

【思路要点】

• 单纯形法模板题，数据很强，错误的实现很可能无法通过Extra Test。
  

【代码】

复制代码#include<bits/stdc++.h> using namespace std; const int MAXN = 55; const long double eps = 1e-8; const long double INF = 1e99; template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, m, type, idn[MAXN], idm[MAXN]; long double a[MAXN][MAXN], ans[MAXN]; void pivot(int l, int e) { swap(idm[l], idn[e]); long double tmp = -a[l][e]; a[l][e] = -1; for (int i = 0; i <= n; i++) if (fabs(a[l][i]) <= eps) a[l][i] = 0; else a[l][i] /= tmp; for (int i = 0; i <= m; i++) { if (i == l) continue; if (fabs(a[i][e]) <= eps) { a[i][e] = 0; continue; } tmp = a[i][e]; a[i][e] = 0; for (int j = 0; j <= n; j++) a[i][j] += a[l][j] * tmp; } } long double simplex() { while (true) { int l = m + 1, e = n + 1; idm[l] = idn[e] = n + m + 1; long double Min = INF, tmp; for (int i = 1; i <= n; i++) if (a[0][i] > eps && idn[i] < idn[e]) e = i; if (e == n + 1) return a[0][0]; for (int i = 1; i <= m; i++) if (a[i][e] < -eps && ((tmp = a[i][0] / -a[i][e]) < Min - eps || tmp < Min + eps && idm[i] < idm[l])) { l = i; Min = tmp; } if (l == m + 1) { printf("Unboundedn"); exit(0); } pivot(l, e); } } long double solve() { long double Min = 0; int l = 0; for (int i = 1; i <= m; i++) if (a[i][0] < Min) { Min = a[i][0]; l = i; } for (int i = 1; i <= n; i++) idn[i] = i; for (int i = 1; i <= m; i++) idm[i] = i + n; if (Min == 0) return simplex(); static long double tmp[MAXN]; for (int i = 0; i <= n; i++) tmp[i] = a[0][i], a[0][i] = 0; idn[++n] = 0; a[0][n] = -1; for (int i = 1; i <= m; i++) a[i][n] = 1; pivot(l, n); if (simplex() < -eps) { printf("Infeasiblen"); exit(0); } for (int i = 1; i <= m; i++) { if (idm[i] != 0) continue; for (int j = 1; j <= n; j++) if (fabs(a[i][j]) > eps) { pivot(i, j); break; } break; } int e = 0; for (int i = 1; i <= n; i++) if (idn[i] == 0) e = i; for (int i = 0; i <= m; i++) swap(a[i][e], a[i][n]); swap(idn[e], idn[n--]); for (int i = 1; i <= m; i++) { if (idm[i] > n) continue; for (int j = 0; j <= n; j++) a[0][j] += a[i][j] * tmp[idm[i]]; } for (int i = 1; i <= n; i++) if (idn[i] <= n) a[0][i] += tmp[idn[i]]; return simplex(); } int main() { read(n), read(m), read(type); for (int i = 1; i <= n; i++) read(a[0][i]); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) read(a[i][j]), a[i][j] = -a[i][j]; read(a[i][0]); } printf("%.10Lfn", solve()); if (type) { memset(ans, 0, sizeof(ans)); for (int i = 1; i <= m; i++) if (idm[i] <= n) ans[idm[i]] = a[i][0]; for (int i = 1; i <= n; i++) printf("%.10Lf ", ans[i]); } return 0; }

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
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
const long double eps = 1e-8;
const long double INF = 1e99;
template <typename T> void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n, m, type, idn[MAXN], idm[MAXN];
long double a[MAXN][MAXN], ans[MAXN];
void pivot(int l, int e) {
swap(idm[l], idn[e]);
long double tmp = -a[l][e]; a[l][e] = -1;
for (int i = 0; i <= n; i++)
if (fabs(a[l][i]) <= eps) a[l][i] = 0;
else a[l][i] /= tmp;
for (int i = 0; i <= m; i++) {
if (i == l) continue;
if (fabs(a[i][e]) <= eps) {
a[i][e] = 0;
continue;
}
tmp = a[i][e]; a[i][e] = 0;
for (int j = 0; j <= n; j++)
a[i][j] += a[l][j] * tmp;
}
}
long double simplex() {
while (true) {
int l = m + 1, e = n + 1;
idm[l] = idn[e] = n + m + 1;
long double Min = INF, tmp;
for (int i = 1; i <= n; i++)
if (a[0][i] > eps && idn[i] < idn[e]) e = i;
if (e == n + 1) return a[0][0];
for (int i = 1; i <= m; i++)
if (a[i][e] < -eps && ((tmp = a[i][0] / -a[i][e]) < Min - eps || tmp < Min + eps && idm[i] < idm[l])) {
l = i;
Min = tmp;
}
if (l == m + 1) {
printf("Unboundedn");
exit(0);
}
pivot(l, e);
}
}
long double solve() {
long double Min = 0; int l = 0;
for (int i = 1; i <= m; i++)
if (a[i][0] < Min) {
Min = a[i][0];
l = i;
}
for (int i = 1; i <= n; i++)
idn[i] = i;
for (int i = 1; i <= m; i++)
idm[i] = i + n;
if (Min == 0) return simplex();
static long double tmp[MAXN];
for (int i = 0; i <= n; i++)
tmp[i] = a[0][i], a[0][i] = 0;
idn[++n] = 0; a[0][n] = -1;
for (int i = 1; i <= m; i++)
a[i][n] = 1;
pivot(l, n);
if (simplex() < -eps) {
printf("Infeasiblen");
exit(0);
}
for (int i = 1; i <= m; i++) {
if (idm[i] != 0) continue;
for (int j = 1; j <= n; j++)
if (fabs(a[i][j]) > eps) {
pivot(i, j);
break;
}
break;
}
int e = 0;
for (int i = 1; i <= n; i++)
if (idn[i] == 0) e = i;
for (int i = 0; i <= m; i++)
swap(a[i][e], a[i][n]);
swap(idn[e], idn[n--]);
for (int i = 1; i <= m; i++) {
if (idm[i] > n) continue;
for (int j = 0; j <= n; j++)
a[0][j] += a[i][j] * tmp[idm[i]];
}
for (int i = 1; i <= n; i++)
if (idn[i] <= n) a[0][i] += tmp[idn[i]];
return simplex();
}
int main() {
read(n), read(m), read(type);
for (int i = 1; i <= n; i++)
read(a[0][i]);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
read(a[i][j]), a[i][j] = -a[i][j];
read(a[i][0]);
}
printf("%.10Lfn", solve());
if (type) {
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= m; i++)
if (idm[i] <= n) ans[idm[i]] = a[i][0];
for (int i = 1; i <= n; i++)
printf("%.10Lf ", ans[i]);
}
return 0;
}

最后

以上就是贪玩心锁最近收集整理的关于【UOJ179】线性规划的全部内容，更多相关【UOJ179】线性规划内容请搜索靠谱客的其他文章。