题目链接：
?pid=2682
题目大意：
有N个城市，每个城市有一个幸福值，如果两个城市A、B的幸福值分别为VA、VB，如果VA是
为Min(Min(VA , VB),|VA-VB|)。
问：现在想要建几条路，使得能够连接所有的城市，所需要建设的最少路程和是多少？
思路：
就是求最小生成树，先用素数筛选法将素数打表，然后根据题意建边。最后就是用Prim模板求
最小生成树就行了。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 660;const int INF = 0xffffff0;int vis[MAXN],low[MAXN],Map[MAXN][MAXN],A[MAXN];int prim(int n){int pos,Min,result = 0;memset(vis,0,sizeof(vis));vis[1] = 1;pos = 1;for(int i = 1; i <= n; i++)if(i != pos)low[i] = Map[pos][i];for(int i = 1; i < n; i++){Min = INF;for(int j = 1; j <= n; j++){if(vis[j]==0 && Min > low[j]){Min = low[j];pos = j;}}result += Min;vis[pos] = 1;for(int j = 1; j <= n; j++){if(vis[j]==0 && low[j] > Map[pos][j]){low[j] = Map[pos][j];}}}return result;}bool Prime[1000100];void IsPrime(){for(int i = 2; i <= 1000000; ++i)Prime[i] = true;for(int i = 2; i <= 1000000; ++i){if(Prime[i]){for(int j = i+i; j <= 1000000; j += i)Prime[j] = false;}}}int father[MAXN];int find(int x){if(x == father[x])return father[x];elsereturn father[x] = find(father[x]);}int main(){int T,N;scanf("%d",&T);IsPrime();while(T–){scanf("%d",&N);for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)Map[i][j] = INF;for(int i = 1; i <= N; ++i)scanf("%d",&A[i]);for(int i = 1; i <= N; ++i)father[i] = i;for(int i = 1; i <= N; ++i){for(int j = i+1; j <= N; ++j){if(Prime[A[i]] || Prime[A[j]] || Prime[A[i]+A[j]]){int x = find(i);int y = find(j);if(x != y)father[x] = y;Map[i][j] = Map[j][i] = min(min(A[i],A[j]),abs(A[i]-A[j]));}}}int flag = 1;for(int i = 1; i <= N; ++i){if(find(i) != find(1))flag = 0;}if(flag)printf("%d\n",prim(N));elseprintf("-1\n");}return 0;}
，吃水不忘挖井人。
