Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贪心+并查集#include <cstdio> #include <algorithm> #include <iostream> using namespace std; typedef pair<int,int> P; const int MAX = 1e5+6; int parent[MAX]; P ps[MAX]; int N; void init() { for(int i = 0;i < MAX;i++) parent[i] = i; } int find(int x) { if(x == parent[x]) return x; return parent[x] = find(parent[x]); } void join(int x,int y) { int p1 = find(x); int p2 = find(y); if(p1 == p2) return; if(p1 > p2) parent[p1] = p2; else parent[p2] = p1; } int main() { while(cin>>N) { init(); for(int i = 0;i < N;i++) scanf("%d%d",&ps[i].first,&ps[i].second); sort(ps,ps+N); int ans = 0; for(int i = N-1;i >= 0;i--) { int able = find(ps[i].second); if(able >= 1) { join(ps[i].second,able-1); ans += ps[i].first; } else continue; } cout<<ans<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator