hdu 2682 Tree
#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
",sum);
else printf("-1
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.