单击666传送 Tree
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
Author Teddy 最小生成树，无非是加了个素数判断，数不是很大，筛一下就好的
#include <cstdio> #include <cmath> #include <cstring> #define INF 0x3f3f3f int map[610][610],s,n; const int N=2000005; bool pri[N]; void Prime(){ pri[0]=1; pri[1]=1; for(int i=2;i<=sqrt(N);i++) if(!pri[i]){ for(int j=i*i;j<=N;j+=i) pri[j]=1; } } int abs(int n){ if(n<0)n=-n; return n; } int min(int a,int b) { return a<b?a:b; } void prim() { s=0; int i,j,next,min; int lowcost[610],visit[610]; memset(visit,0,sizeof(visit)); for(i=0;i<n;++i) lowcost[i]=map[0][i]; visit[0]=1; for(i=1;i<n;++i) { min=INF; for(j=0;j<n;++j) { if(!visit[j]&&min>lowcost[j]) { min=lowcost[j]; next=j; } } if(min==INF) { printf("-1\n"); return ; } s+=min; visit[next]=1; for(j=0;j<n;++j) { if(!visit[j]&&lowcost[j]>map[next][j]) lowcost[j]=map[next][j]; } } printf("%d\n",s); } int main() { Prime(); int t,a[610],i,j; scanf("%d",&t); while(t--) { memset(map,INF,sizeof(map)); scanf("%d",&n); for(i=0;i<n;++i) scanf("%d",&a[i]); for(i=0;i<n;++i) { for(j=0;j<n;++j) { if(!pri[a[i]]||!pri[a[j]]||!pri[a[i]+a[j]]) map[i][j]=map[j][i]=min(min(a[i],a[j]),abs(a[i]-a[j])); } } prim(); } return 0; }