首页 > ACM题库 > HDU-杭电 > hdu 2682 Tree-最小生成树-[解题报告]C++
2014
02-13

hdu 2682 Tree-最小生成树-[解题报告]C++

Tree

问题描述 :

There are N (2<=N<=600) cities,each has a value of happiness,we consider two cities A and B whose value of happiness are VA and VB,if VA is a prime number,or VB is a prime number or (VA+VB) is a prime number,then they can be connected.What’s more,the cost to connecte two cities is Min(Min(VA , VB),|VA-VB|).
Now we want to connecte all the cities together,and make the cost minimal.

输入:

The first will contain a integer t,followed by t cases.
Each case begin with a integer N,then N integer Vi(0<=Vi<=1000000).

输出:

The first will contain a integer t,followed by t cases.
Each case begin with a integer N,then N integer Vi(0<=Vi<=1000000).

样例输入:

2
5
1
2
3
4
5

4
4
4
4
4

样例输出:

4
-1

http://acm.hdu.edu.cn/showproblem.php?pid=2682

题目大意:T组测试实例,每组实例有n个城市,每个城市有一个幸福指数V;如果 Va 或 Vb 或 Va+Vb 是素数的话,两个城市可以连接起来;将两个城市连接起来所需的花费为min(min(Va,Vb),|Va-Vb|);如果所有的城市都能连接起来的话输出最小花费,否则输出“-1”;

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define MAX 1000006
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int prime[MAX];
int set[606];
struct node
{
	int a,b,len;
}map[180000];

int cmp(const void* a,const void*b)
{
	return (*(node*)a).len-(*(node*)b).len;
}

//并查集
int find(int x)
{
	if(set[x]!=x){
		set[x]=find(set[x]);
	}
	return set[x];
}
int Union(int a,int b)
{
	int x=find(a);
	int y=find(b);
	if(x==y)
		return 0;
	set[x]=y;
	return 1;
}

int main()
{
	int T,n,i,j,k,temp,cnt,cost;

	//筛选法求素数
	memset(prime,0,sizeof(prime));
	prime[0]=1;
	prime[1]=1;
	for(i=2;i<MAX;i++){
		if(prime[i]==0){
			for(j=2;j<MAX;j++){
				temp=i*j;
				if(temp>MAX)break;
				prime[temp]=1;
			}
		}
	}
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&set[i]);
		}
		
		//建图
		for(i=0,k=0;i<n;i++){
			for(j=i+1;j<n;j++){
				if(prime[set[i]]==0 || prime[set[j]]==0 || prime[set[i]+set[j]]==0){
					map[k].a=i;
					map[k].b=j;
					map[k++].len=min(min(set[i],set[j]),abs(set[i]-set[j]));
				}
			}
		}
		qsort(map,k,sizeof(map[0]),cmp);

		for(i=0;i<n;i++){
			set[i]=i;
		}
		for(i=0,cnt=0,cost=0;i<k;i++){
			if(Union(map[i].a,map[i].b)==1){
				cost+=map[i].len;
				cnt++;
			}
		}
		if(cnt==(n-1))
			printf("%d\n",cost);
		else
			printf("-1\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/crazy_xiaohe/article/details/8882947


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.