【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;
}

最后

以上就是贪玩心锁为你收集整理的【UOJ179】线性规划的全部内容，希望文章能够帮你解决【UOJ179】线性规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。