题解 P3265 【[JLOI2015]装备购买】

这题xswl，我把\(m\)打成\(n\)得了\(90\),一看数据……

Solution [JLOI2015]装备购买

线性基，高斯消元

---

我们把所有装备的属性排成一个矩阵，那么我们可以购买的最大的装备数量就是这个矩阵的秩

然后这个东西就可以高斯消元来做了，普通的高斯消元对于每个主元\(x_i\)，选取前\(i-1\)列为\(0\),第\(i\)列绝对值最大的行向量进行消元，这样可以提高数值稳定性，但是这里我们同时要求权值之和最小，我们就贪心的在符合条件的行向量中选权值最小的即可，因此可能略微炸精度

#include <iostream>
#include <algorithm>
using namespace std;
typedef long double type;
const int maxn = 512;
const type eps = 1e-6;
type mat[maxn][maxn];
inline type mabs(type x){return x > 0 ? x : -x;}
inline bool iszero(type x){return mabs(x) < eps;}
int n,m,ans1,ans2,cost[maxn];
inline void gauss(){
    for(int i = 1;i <= n;i++){
        int r = i;
        while(r <= n && iszero(mat[r][i]))r++;
        if(r == n + 1)return;
        for(int j = r + 1;j <= n;j++)
            if(!iszero(mat[j][i]) && cost[j] < cost[r])r = j;
        swap(mat[i],mat[r]),swap(cost[i],cost[r]);
        ans1 += 1,ans2 += cost[i];
        for(int j = i + 1;j <= n;j++){
            type f = mat[j][i] / mat[i][i];
            for(int k = i;k <= n;k++)
                mat[j][k] -= mat[i][k] * f;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> mat[i][j];
    for(int i = 1;i <= n;i++)
        cin >> cost[i];
    gauss();
    cout << ans1 << " " << ans2 << '\n';
    return 0;
}