Tree Time Limit: 6000/2000 MS (
Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1954 Accepted Submission(s): 573
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
题意：两个数A和B， A或B或者A+B是素数就表示A与B能连通。A与B连通的费用是A，B，A-B的绝对值这三个数中最小的值。 先给出n个数，问将他们都连通的最小费用。
最小生成树，判断素数是要打表。
prim算法，代码如下：
#include
#include
#include
#define INF 0x3f3f3f int map[610][610],sum,prime[1000010],n; void is_primes()//素数打表 { int i,j; prime[0]=prime[1]=1; for(i=2;i*i<=1000000;++i) { if(prime[i]) continue; for(j=i*i;j<=1000000;j=i+j) prime[j]=1; } } int min(int a,int b) { return a
lowcost[j]) { min=lowcost[j]; next=j; } } if(min==INF) { printf(-1 ); return ; } sum+=min; visit[next]=1; for(j=0;j
map[next][j]) lowcost[j]=map[next][j]; } } printf(%d ,sum); } int main() { is_primes(); int t,a[610],i,j; scanf(%d,&t); while(t--) { memset(map,INF,sizeof(map)); scanf(%d,&n); for(i=0;i
?
|