装备购买

AcWing-209-装备购买

分析

见《进阶指南》第165页。

实现

#include <iostream>
#include <cmath>
using namespace std;

const int N = 510;
const double eps = 1e-8;
int n, m;
long double a[N][N];
int p[N];
int dim, min_cost;

void Gauss () {
    int r, c;
    for (c = 1, r = 1; c <= m; ++ c) {
        // ---------- 错误 ----------
        // 如果 fabs(a[r][c]) < eps 且 p[r] 最小
        // 那么程序会死循环
        int idx = r;
        for (int i = r; i <= n; ++ i)
            if (fabs(a[i][c]) > eps && p[i] < p[idx])
                idx = i;
        if (fabs(a[idx][c]) < eps) continue;
        // ---------- 正确 ----------
        int idx = 0;
        for (int i = r; i <= n; ++ i)
            if (fabs(a[i][c]) > eps && (idx == 0 || p[i] < p[idx]))
                idx = i;
        if (idx == 0) continue;

        min_cost += p[idx];
        swap(a[r], a[idx]);
        swap(p[r], p[idx]);

        for (int i = 1; i <= n; ++ i) {
            if (i == r) continue;
            long double rate = a[i][c] / a[r][c];
            for (int j = c; j <= m; ++ j)
                a[i][j] -= rate * a[r][j];
        }
        ++ r;
    }
    dim = r - 1;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            cin >> a[i][j];
    for (int i = 1; i <= n; ++ i) cin >> p[i];

    Gauss();
    cout << dim << ' ' << min_cost << endl;
    return 0;
}