最小生成树水题
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int num,n,a[610];
int f[610];
bool prim[2000010];
struct eadge
{
int st,end,w;
}e[180000];
int MIN(int a,int b)
{
if(a>b)return b;
return a;
}
void adde(int x,int y,int w)
{
e[num].st=x;
e[num].end=y;
e[num].w=w;
num++;
}
int cmp(const void *a,const void *b)
{
struct eadge *c,*d;
c=(struct eadge *)a;
d=(struct eadge *)b;
return c->w-d->w;
}
int find(int a)
{
if(a!=f[a])
f[a]=find(f[a]);
return f[a];
}
int main()
{
int i,j,temp,t,x,y;
prim[1]=true;
for(i=2;i<=1500;i++)
if(prim[i]==false)
{
for(j=2*i;j<=2000000;j=j+i)
prim[j]=true;
}
scanf("%d",&t);
while(t--)
{
num=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=i;
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
if(prim[a[i]]==0||prim[a[j]]==0||prim[a[i]+a[j]]==0)
{
temp=MIN(MIN(a[i],a[j]),abs(a[i]-a[j]));
adde(i,j,temp);
}
}
qsort(e,num,sizeof(e[0]),cmp);
int sum=0;
j=0;
for(i=0;i<num;i++)
{
if(j==n-1)break;
x=find(e[i].st);
y=find(e[i].end);
if(x==y)continue;
f[x]=find(f[y]);
sum+=e[i].w;
j++;
}
if(j==n-1)
printf("%d\n",sum);
else printf("-1\n");
}
return 0;
}