Tree
Time Limit: 6000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1847Accepted Submission(s): 541
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
251234544444
Sample Output
4-1
Author
Teddy
Source
2009浙江大学计算机研考复试（机试部分）——全真模拟
这道水题害我wa了 33次 我也是醉了 ，多亏我是在自己开的diy里面提交的，不然我还不哭死在厕所。。。
先来分析一下这道题，很清楚，就是一个最小生成树的模板题，也就是多了一个素数的判定，为避免超时，
可以用筛选素数打表法，接下来就是关于克鲁斯卡尔算法与 prime 算法的 选择问题，实际上都可以，此处
我更倾向于prime算法，便使用我的经验书写了，测试数据，很水，知道不能全信，又检查了一遍看是否
会出现错码，确认无误之后，提交，果断wa。后来 lz又 修改了一些可能存在错误的地方，（后来证实都是
没有问题的）又提交了9次，可惜此次wa，lz当时的心情，已哭晕在厕所。测试结束之后，找到了这道题，
调试了一天（因为要上课，只能利用课余时间，勉强四个小时吧），将所有可能尝试了n遍，最后终于只因
在喧哗中多看了码一眼，抱着试一试的心情，哇，终于ac！！！lz突然有种壮士抹腕，屌丝登上事业巅峰，
出任CTO ，，迎接白富美的自豪！好了，还是说正题吧！代码如下：
//++ 史上第一坑，我都开始质疑我的编程习惯了，注释的部分是 wa了 30多次的代码 //将宏定义 改成直接调用algorithm库里面的函数直接就对了。。。。之前的有道题//同样的代码使用了宏定义，这样更节省了时间，果断AC，于是当时决定使用宏定义，//看来我该好好反省一下自己的人生了！ #include<stdio.h>#include<string.h>#include<stdlib.h>//#define min(a,b) a>b?b:a#include<algorithm>using namespace std;#define inf 0xfffffffint a[2000200];int map[1100][1100],dis[1100],visit[1100],b[1100];int n;void f(){int i,j;a[1]=1,a[0]=1;for(i=2;i*i<=2000000;i++){if(!a[i]){for(j=i*i;j<=2000000;j+=i){a[j]=1;}}}}void prime(){int i,j,pos=1,min,sum=0;//此处的sum可定义为__int64 位的 避免超出 但是这道题数据很水 ，上面判定素数的时候定义到100万就能ＡＣ memset(visit,0,sizeof(visit));for(i=1;i<=n;++i){dis[i]=map[1][i];}visit[1]=1;for(i=1;i<n;++i){min=inf;for(j=1;j<=n;++j){if(!visit[j]&&dis[j]<min){pos=j;min=dis[j];}}if(min==inf){printf("-1\n");return ;}visit[pos]=1;sum+=min;for(j=1;j<=n;++j){if(!visit[j]&&dis[j]>map[pos][j]){dis[j]=map[pos][j];}}}printf("%d\n",sum);}int main(){int t;int i,j;scanf("%d",&t);f();while(t–){scanf("%d",&n);for(i=1;i<=n;++i){scanf("%d",&b[i]);}for(i=1;i<=n;++i){for(j=1;j<=n;++j){if(i==j)map[i][j]=0;elsemap[i][j]=inf;}}for(i=1;i<=n;++i){for(j=i+1;j<=n;++j){if( (!(a[b[i]])) || !a[b[j]] || !a[b[i]+b[j]]){int minx=min(min(b[i],b[j]),abs(b[i]-b[j]));if(minx<map[i][j])map[i][j]=map[j][i]=minx;}}}prime();}return 0;}
因为冲动会做下让自己无法挽回的事情。
