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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求测试数据, 2天了,xxxxxxxxxxxxxxxxx谢

Posted by qmzqhqy at 2008-08-23 19:47:10 on Problem 2054
//求测试数据, 2天了,xxxxxxxxxxxxxxxxx谢
#include<iostream>
using namespace std;

int c[1010], pre[1010], next[1010];

double c1[1010];
int n, r;
int findmax(double c1[])//非r的最大节点
{
	int i, th;
	double max;
	max = 0;
	th = 0;
	for(i = 1; i <= n; i++)
	{
		if(c1[i] > max && i != r)
		{
			max = c1[i];
			th = i;
		}
	}
	return th;
}

void uni(int d, int pred)
{
	int i;
	for(i = 1; i <= n; i++)
		if(pre[i] == d)
			pre[i] = pred;
	if(pred != r)
		c1[pred] = (c1[d] + c1[pred])/2;
	c1[d] = 0;
	for(i = pred; next[i] != 0; i = next[i]);

	next[i] = d;

}

int main()
{
	int i, d, e, sum;
	cin>>n>>r;

	while(n || r)
	{
		pre[r] = r;
		memset(next, 0, sizeof(next));
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &c[i]);
			c1[i] = c[i];
		}
		for(i = 1; i < n; i++)
		{
			scanf("%d%d", &d, &e);
			pre[e] = d;
		}
		for(i = 1; i < n; i++)
		{
			d = findmax(c1);
			uni(d, pre[d]);
		}
		sum = 0; 
		d = 1;
		for(i = r; i != 0; i = next[i])
		{
			sum += d*c[i];
			d++;
		}
		cout<<sum<<endl;

		cin>>n>>r;
	}
	return 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