Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求纠错,用multiset做的贪心,给跪了

Posted by AndrewWayne at 2019-01-31 14:23:45 on Problem 2054
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
int father[1010], son[1010][1010], top[1010], cnt[1010], sum[1010];
int n, r, a[1010], u, v, ans;
double val[1010];
struct Node{
	int id;
	const bool operator<(const Node &v)const{
		return val[id] > val[v.id];
	}
	Node(int k):id(k){}
	Node(){}
};
multiset<Node> bst;
int main(){
	//freopen("data.in", "r", stdin);
	while(cin >> n >> r){
		bst.clear();
		ans = 0;
		memset(top, 0, sizeof(top));
		memset(father, 0, sizeof(father));
		if(!(n+r))
			return 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			cnt[i] = 1;
			sum[i] = a[i];
			val[i] = a[i];
			if(i != r)
				bst.insert(Node(i));
			ans += a[i];
		}
		for(int i = 1; i < n; i++){
			cin >> u >> v;
			son[u][++top[u]] = v;
			father[v] = u;
		}
		while(!bst.empty()){
			set<Node>::iterator p = bst.begin();
			int u = (p -> id);
			cerr << u << endl;
			bst.erase(p);
			ans += cnt[father[u]] * sum[u];
			for(int i = 1; i <= top[u]; i++){
				father[son[u][i]] = father[u];
				son[father[u]][++top[father[u]]] = son[u][i];
			}
			if(father[u] != r)
				bst.erase(father[u]);
			cnt[father[u]] += cnt[u];
			sum[father[u]] += sum[u];
			val[father[u]] = (double)sum[father[u]]/cnt[father[u]];
			if(father[u] != r)
				bst.insert(father[u]);
		}
		cout << ans << endl;
	}
	return 0;
}
/*
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
7 1
1 3 9 4 1 10 1
1 2 
1 3
2 4
2 5
3 6
3 7
11 1
1 100 9 99 3 3 8 7  11 18 10
1 2
1 3
2 4
3 5
3 6
5 7
7 8
7 9
8 10
10 11
0 0
*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator