洛谷 [P3265] 装备购买

线性基

通过题目描述可以感觉到就是要求线性基,

线性基的求法是高斯消元,消完以后剩下的x的系数非 0 的就是线性基

本题有一个贪心策略,每次挑选价格最小的来消掉其他的元

//可以快排预处理

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

const int MAXN = 505;

int b[MAXN], n, m;

long double a[MAXN][MAXN];

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 >> b[i];

	for(int i = 1; i <= m; i++) {

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

			if(fabs(a[j][i]) > 1e-4 && b[j] < b[i]) {

				for(int k = 1; k <= n; k++) swap(a[i][k], a[j][k]);

				swap(b[i], b[j]);

			}

		}

		if(!a[i][i]) continue;

		for(int j = 1; j <= n; j++) {

			if(i == j) continue;

			long double rate = (a[j][i] / a[i][i]);

			for(int k = i; k <= m; k++) {

				a[j][k] -= a[i][k] * rate;

			}

		}

	}

	int cnt = 0, ans = 0;

	for(int i = 1; i <= min(n, m); i++) {

		if(fabs(a[i][i]) > 1e-4) cnt++, ans += b[i];

	}

	printf("%d %d\n", cnt, ans);

	return 0;

}

线性基优化版

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define eps 1e-5

using namespace std;

const int MAXN = 505;

int n, m, nxt[MAXN], cnt, ans;

struct qwq{

	long double num[MAXN];

	int val;

	bool operator < (const qwq &b) const{

		return this -> val < b.val;

	}

}a[MAXN];

bool f[MAXN];

int main() {

	cin >> n >> m;

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

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

			cin >> a[i].num[j];

		}

	}

	for(int i = 1; i <= n; i++) cin >> a[i].val;

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

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

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

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

				if(!f[j]) {

					f[j] = 1;

					cnt++;

					ans += a[i].val;

					nxt[j] = i;

					break;

				}else{

					long double rate = a[i].num[j] / a[nxt[j]].num[j];

					for(int k = j; k <= n; k++) a[i].num[k] -= rate * a[nxt[j]].num[k];

				}

			}

		}

	}

	printf("%d %d\n", cnt, ans);

	return 0;

}

巴特西

洛谷 [P3265] 装备购买

线性基

最新文章

热门文章