BZOJ1061:单纯形法模板

#include <cstdio> #include <algorithm> #include <cstring> const int N = 1000 + 5; const int M = 10000 + 5; double c[N], A[M][N], b[M], ans; int n, m; void pivot(int id, int p) { A[id][p] = 1 / A[id][p]; b[id] *= A[id][p]; for (int i = 1; i <= n; i++) if (i ^ p) A[id][i] *= A[id][p]; for (int i = 1; i <= m; i++) { if ((i ^ id) && A[i][p]) { for (int j = 1; j <= n; j++) if (j ^ p) A[i][j] -= A[i][p] * A[id][j]; b[i] -= A[i][p] * b[id]; A[i][p] *= -A[id][p]; } } for (int i = 1; i <= n; i++) if (i ^ p) c[i] -= c[p] * A[id][i]; ans += c[p] * b[id]; c[p] *= -A[id][p]; } double solve() { while (true) { int p, Min_id; for (p = 1; p <= n; p++) if (c[p] > 0) break; if (p == n + 1) return ans; double Min = 0x3f3f3f3f; for (int i = 1; i <= m; i++) if (A[i][p] > 0 && Min > b[i] / A[i][p]) { Min = b[i]; Min_id = i; } if (Min == 0x3f3f3f3f) return Min; pivot(Min_id, p); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lf", &c[i]); for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d%lf", &x, &y, &b[i]); for (int j = x; j <= y; j++) A[i][j] = 1; } printf("%.0lf\n", solve()); return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注