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 127 128 129 130 131 132 133 134 135 136 137 138 139 140
|
#include <algorithm> #include <cstdio> #include <cstring>
static int const N = 45; static long double const EPS = 1e-8; int t;
int pm(long double const &n) { return (n < 0 ? -n : n) < EPS ? 0 : n < 0 ? -1 : 1; }
class Array { private: long double arr[N];
public: int size;
long double &operator[](int const &n) { return arr[n]; }
long double max() { return *std::max_element(arr + 1, arr + size + 1); }
void operator/=(long double n) { for (int i = 0; i <= size; ++i) arr[i] /= n; }
void add(Array a, long double n) { for (int i = 0; i <= size; ++i) arr[i] += a[i] * n; } };
class Simplex { private: int id[N]; Array tmp;
void pivot(int e, int v) { a[e] /= a[e][v]; for (int i = 0; i <= m; ++i) if (i != e) a[i].add(a[e], -a[i][v]); id[e] = v; }
int simplex(int n, int m) { for (; pm(a[0].max()) > 0;) { int col = -1, row = -1; for (int i = 1; i <= n; ++i) if (pm(a[0][i]) > 0) { col = i; break; } long double mn = 1e100, tmp; for (int i = 1; i <= m; ++i) if (pm(a[i][col]) > 0 && ((tmp = pm(a[i][0] / a[i][col] - mn)) < 0 || tmp == 0 && id[i] < id[row])) mn = a[i][0] / a[i][col], row = i; if (row == -1) return 1; pivot(row, col); } return 0; }
public: int n, m; Array ans, a[N];
int solve() { for (int i = 1; i <= m; ++i) a[i][n + i] = 1, id[i] = n + i; int row = -1; long double mn = 1e100; for (int i = 1; i <= m; ++i) if (a[i][0] < mn) mn = a[i][0], row = i; if (pm(mn) < 0) { for (int i = 1; i <= n; ++i) tmp[i] = a[0][i], a[0][i] = 0; for (int i = 0; i <= m; ++i) a[i][n + m + 1] = -1; for (int i = 0; i <= m; ++i) a[i].size = n + m + 1; pivot(row, n + m + 1), simplex(n + m + 1, m); if (pm(a[0][0]) != 0) return -1; for (int i = 1; i <= m; ++i) if (id[i] == n + m + 1) { for (int j = 1; j <= n + m; ++j) if (pm(a[i][j]) != 0) { pivot(i, j); break; } break; } for (int i = 1; i <= n; ++i) a[0][i] = tmp[i]; for (int i = 1; i <= m; ++i) a[0].add(a[i], -a[0][id[i]]); } for (int i = 0; i <= m; ++i) a[i].size = n + m; int ret = simplex(n + m, m); if (!ret) for (int i = 1; i <= m; ++i) if (id[i] <= n) ans[id[i]] = a[i][0]; return ret; } } solver;
int main() { scanf("%d%d%d", &solver.n, &solver.m, &t); for (int i = 1; i <= solver.n; ++i) scanf("%Lf", &solver.a[0][i]); for (int i = 1; i <= solver.m; scanf("%Lf", &solver.a[i++][0])) for (int j = 1; j <= solver.n; ++j) scanf("%Lf", &solver.a[i][j]); int res = solver.solve(); if (res == -1) puts("Infeasible"); else if (res == 1) puts("Unbounded"); else { printf("%.10Lf\n", -solver.a[0][0]); if (t == 1) { for (int i = 1; i <= solver.n; ++i) printf("%.10Lf ", solver.ans[i]); puts(""); } } return 0; }
|