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)