欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【POJ-1456】 Supermarket

程序员文章站 2022-06-02 19:54:32
...

【POJ-1456】 Supermarket
【POJ-1456】 Supermarket

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int SIZE = 1 << 20;
vector<pair <int,int> > vec;
int fa[SIZE];

bool cmp(pair<int,int> a,pair<int,int> b) {
	return a.first > b.first;
}

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

void merge(int x,int y) {
	fa[get(x)] = get(y);
}

int main() {
	int n;
	while (cin >> n) {
		int ans = 0, maxn = 0; vec.clear();
		int a, b;
		for (int i = 1; i <= n; ++i) {
			cin >> a >> b;
			vec.push_back(make_pair(a,b));
			maxn = max(maxn, b);
		}
		sort(vec.begin(), vec.end(), cmp);
		for (int i = 0; i <= maxn ; ++i) {
			fa[i] = i;
		}
		for (int i = 0; i < n; ++i) {
			int w = vec[i].first, v = vec[i].second;
			int root = get(v);
			if (root > 0) {
				ans += w; merge(root,root-1);
			}
		}
		cout << ans << endl;
	}
	return 0;
}
相关标签: ACM-ICPC题集