【POJ-1456】 Supermarket
程序员文章站
2022-06-02 19:54:32
...
#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;
}