BZOJ 4004 [JLOI2015]装备购买

题目链接

题解

非常正常的线性基！

但是我不会线性基……

（吐槽：#define double long double 才过……）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#define space putchar(' ')

#define enter putchar('\n')

typedef long long ll;

using namespace std;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

#define double long double

const int N = 505;

const double eps = 1e-5;

int n, m, ins[N], ans, cnt;

struct vec {

    int val;

    double x[N];

    bool operator < (const vec &b) const{

	return val < b.val;

    }

} a[N];

void gauss(){

    for(int i = 1; i <= n; i++)

	for(int j = 1; j <= m; j++)

	    if(fabs(a[i].x[j]) > eps){

		if(!ins[j]){

		    cnt++, ans += a[i].val;

		    ins[j] = i;

		    break;

		}

		double rate = a[i].x[j] / a[ins[j]].x[j];

		for(int k = m; k >= j; k--)

		    a[i].x[k] -= rate * a[ins[j]].x[k];

	    }

}

int main(){

    read(n), read(m);

    for(int i = 1; i <= n; i++)

	for(int j = 1; j <= m; j++)

	    read(a[i].x[j]);

    for(int i = 1; i <= n; i++)

	read(a[i].val);

    sort(a + 1, a + n + 1);

    gauss();

    write(cnt), space, write(ans), enter;

    return 0;

}

巴特西

BZOJ 4004 [JLOI2015]装备购买 | 线性基

题目链接

题解

最新文章

热门文章