Tree
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1533 Accepted Submission(s): 433
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.
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).
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
2
3
4
5
4
4
4
4
4
4
4
4
Sample Output
4
-1
思路：由于题目对能相连的点有限制，必须将这些点处理，能相连的点合并到一个集合中，最后查看是否所有点都在一个集合里，若都在说明是一个连通图，存在最小生成树，否则图不连通，不存在最小花费。
AC代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int CityHappy[],vis[];
int isprime[],dist[];
int map[][],n;
int father[],depth[];
void init_B()
{
int i;
for(i = ;i <= n;i ++)
{
father[i] = i;
depth[i] = ;
}
} int find(int x)
{
if(x == father[x])
return x;
return father[x] = find(father[x]);
} void unit(int x,int y)
{
x = find(x);
y = find(y);
if(x == y)
return ;
if(depth[x] > depth[y])
father[y] = x;
else
{
if(depth[x] < depth[y])
father[x] = y;
else
{
father[x] = y;
depth[y]++;
}
}
} void prime()
{
int i,j;
isprime[] = isprime[] = ;
for(i = ;i <= 1e6;i ++)
{
if(!isprime[i])
{
for(j = i << ;j <= 1e6;j += i)
isprime[j] = ;
}
}
} int judge(int a,int b)
{
if(!isprime[a] || !isprime[b])
return ;
if(!isprime[a+b])
return ;
return ;
} int min(int a,int b)
{
return a < b?a:b;
} void opration()
{
int i,j,a,b;
init_B();
for(i = ;i <= n;i ++)
{
for(j = ;j <= n;j ++)
{
if(i != j)
{
a = CityHappy[i];
b = CityHappy[j];
if(judge(a,b))
{
map[i][j] = min(min(a,b),abs(a-b));
map[j][i] = map[i][j];
unit(i,j);
}
else
map[i][j] = map[j][i] = << ;
}
}
}
} void init()
{
int i;
memset(vis,,sizeof(vis));
for(i = ;i <= n;i ++)
dist[i] = map[][i];
} int main()
{
int t,i,j,k,cnt,min,sum;
scanf("%d",&t);
prime();
while(t--)
{
sum = cnt = ;
scanf("%d",&n);
for(i = ;i <= n;i ++)
scanf("%d",&CityHappy[i]);
opration();
init();
for(i = ;i <= n;i ++)
{
if(i == find(i))
cnt++;
if(cnt == )
break;
}
if(cnt == )
{
printf("-1\n");
continue ;
}
for(i = ;i < n;i ++)
{
min = << ;
for(j = ;j <= n;j ++)
{
if(!vis[j] && min > dist[j])
{
min = dist[j];
k = j;
}
}
vis[k] = ;
if(min != << )
sum += min;
for(j = ;j <= n;j ++)
{
if(!vis[j] && dist[j] > map[k][j])
dist[j] = map[k][j];
}
}
printf("%d\n",sum);
}
return ;
}