HDU 2682 Tree（Kruskal算法求解MST）

题目：

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.

InputThe first will contain a integer t,followed by t cases.
Each case begin with a integer N,then N integer Vi(0<=Vi<=1000000).OutputIf the all cities can be connected together,output the minimal cost,otherwise output "-1";Sample Input

Sample Output

4
-1
题意描述：
题目还是有点意思的，但是还是改变不了使水题的本质。
输入结点的个数以及每个结点的权值
计算并输出有特殊要求的最小生成树
解题思路：
属于最小生成树问题，按照数据的格式，使用Kruskal算法。
代码实现：

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<algorithm>
 4 using namespace std;
 5 struct edge
 6 {
 7     int u,v,w;
 8 };
 9 struct edge e[610*610];//大数组申请全局变量 
10 int f[610];
11 bool cmp(struct edge x,struct edge y)
12 {
13     return x.w<y.w;
14 }
15 int getf( int v);
16 int merge(int c,int u);
17 int isp(int n);    
18 
19 int main()
20 {
21     int t,i,n,c[610],j,k,count,sum;
22     scanf("%d",&t);
23     while(t--)
24     {
25         scanf("%d",&n);
26         for(i=1;i<=n;i++)
27             scanf("%d",&c[i]);
28         k=1;
29         for(i=1;i<=n;i++)
30         {
31             for(j=i+1;j<=n;j++)
32             {
33                 if(isp(c[i]) || isp(c[j]) || isp(c[i]+c[j]))
34                 {
35                     e[k].u=i;
36                     e[k].v=j;
37                     e[k++].w = min(min(c[i],c[j]),abs(c[i]-c[j]));
38                 }
39             }
40         }
41         sort(e+1,e+k,cmp);
42         for(i=1;i<=n;i++)
43             f[i]=i;
44         count = 0;
45         sum=0;
46         for(i=1;i<k;i++)
47         {
48             if(  merge(e[i].u,e[i].v) )
49             {
50                 count++;
51                 sum += e[i].w;
52             }
53             if(count == n-1)
54                 break;
55         }
56         
57         if(count == n-1)
58         printf("%d
",sum);
59         else
60         printf("-1
");
61     }
62     return 0;
63 }
64 
65 int getf( int v)
66 {
67     if(f[v]==v)
68     return v;
69     else
70     {
71         f[v]=getf(f[v]);
72         return f[v];
73     }
74 }
75 int merge(int v,int u)
76 {
77     int t1,t2;
78     t1=getf(v);
79     t2=getf(u);
80     if(t1 != t2)
81     {
82         f[t2]=t1;
83         return 1;
84     }
85     return 0;
86 }
87 int isp(int n)
88 {
89     if(n==1)//1不是素数 
90         return 0; 
91     int k,i;
92     k=(int)sqrt(n);
93     for(i=2;i<=k;i++)
94     {
95         if(n % i==0)
96             return 0;
97     }
98     return 1;
99 }

易错分析：

1、程序直接强制结束，可能是数组开的太大，放在全局变量的位置就可以了。

2、判断素数的过程中，1不是素数（代码功力）