Tree
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1139 Accepted Submission(s): 314
Problem Description
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.
Input
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).
Output
If the all cities can be connected together,output the minimal cost,otherwise output "-1";
Sample Input
2
5
1
2
3
4
5
4
4
4
4
4
Sample Output
4
-1
我的代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int p[1000];
int prim[1000000];
struct node
{
int a,b,dis;
}e[200000];
int min(int a,int b)
{
return a<b?a:b;
}
void prime()
{
int i,j;
for(i=0;i<1000000;i++) prim[i]=1;
for(j=2;j<1000000;j++)
for(i=2;i*i<=j;i++)
{
if(j%i==0) prim[j]=0;
break;
}
prim[2]=1;
prim[0]=prim[1]=0;
}
bool cmp(const node &a,const node &b)
{
return a.dis<b.dis;
}
int find(int a)
{
if(a==p[a]) return a;
else return find(p[a]);
}
void Union(int a,int b)
{
int x=p[a];
int y=p[b];
p[x]=y;
}
int main()
{
int t,n,i,j,k,v[605],T,ans;
prime();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
k=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(prim[v[i]]||prim[v[j]]||prim[v[i]+v[j]])
{
e[k].a=i;
e[k].b=j;
e[k].dis=min(min(v[i],v[j]),abs(v[i]-v[j]));
k++;
}
}
sort(e,e+k,cmp);
ans=T=0;
for(i=0;i<1000;i++)
p[i]=i;
for(i=0;i<k;i++)
{
if(find(e[i].a)!=find(e[i].b))
{
Union(e[i].a,e[i].b);
ans+=e[i].dis;
T++;
}
if(T==n-1) break;
}
if(T==n-1) printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}
3 个解决方案
#1
原来prime number 是素数的意思...
#2
请问你想要完成什么功能??可不可以给点注释..让我们帮你想想办法..还有,请把你出现的错误结果给出来.让大家帮你分析 一下...我是真的想帮你..可是我英文不好的....
#3
自己顶啊，请大家帮帮忙哇
#1
原来prime number 是素数的意思...
#2
请问你想要完成什么功能??可不可以给点注释..让我们帮你想想办法..还有,请把你出现的错误结果给出来.让大家帮你分析 一下...我是真的想帮你..可是我英文不好的....
#3
自己顶啊，请大家帮帮忙哇