【題解】洛谷P3265（同bzoj4004）[JSOI2015]裝備購買 高斯消元

題目連結

題目描述

輸入輸出格式

輸入格式：

第一行兩個數 n;m。接下來 n 行，每行 m 個數，其中第 i 行描述裝備 i 的各項屬性值。接下來一行 n 個數，其中 ci 表示購買第 i 件裝備的花費。

輸出格式：

一行兩個數，第一個數表示能夠購買的最多裝備數量，第二個數表示在購買最多數量的裝備的情況下的最小花費

輸入輸出樣例

輸入樣例#1：

3 3

1 2 3

3 4 5

2 3 4

1 1 2

輸出樣例#1：

2 2

說明

如題目中描述，選擇裝備 1 裝備 2，裝備 1 裝備 3，裝備 2 裝備 3 均可，但選擇裝備 1 和裝備 2 的花費最小，為 2。

對于 100% 的資料, 1 <= n;m <= 500; 0 <= aj <= 1000。

把n件裝備看成n個長度為m的向量，求線性空間的基。

将屬性看成系數矩陣，高斯消元求出該矩陣的秩。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define _rep(i,a,b) for(int i=(a);i<=(b);i++)
typedef long double lb;
const double eps=;
const int N=;
int n,m,cnt,cost;
struct node{
    lb buff[N];//屬性 
    int c;//價格 
    bool operator<(const node&rhs)const{
    return c<rhs.c;}
}arm[N];
int z[N];//基底 
int main()
{
    //freopen("in.txt","r",stdin);
    std::ios::sync_with_stdio(false);//這玩意和freopen一起用就炸了 
    cin>>n>>m;
    _rep(i,,n)_rep(j,,m)cin>>arm[i].buff[j];
    _rep(i,,n)cin>>arm[i].c;
    sort(arm+,arm+n+);
    _rep(i,,n)_rep(j,,m)if(fabs(arm[i].buff[j])>eps)
    {
        if(!z[j]){z[j]=i;cnt++;cost+=arm[i].c;break;}
        else
        {
            lb p=arm[i].buff[j]/arm[z[j]].buff[j];
            _rep(k,j,m)arm[i].buff[k]-=p*arm[z[j]].buff[k];
        }
    }
    printf("%d %d\n",cnt,cost);
}
           

總結

高斯消元求線性基