HDU2682 Tree 题解 【最小生成树】【图论】【Kruskal】

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

2

5

1

2

3

4

5

4

4

4

4

4

Sample Output

4

-1

解题报告

题意就是有N座城市，每个城市有一定的幸福值a[i]。对于任意两个城市i和j，如果a[i]，a[j]，a[i]+a[j]中任意一者的值为素数，那么他们的边权就是min(min(a[i],a[j]),abs(a[i]-a[j]))。问题就是这一幅图的最小生成树。

显然，边一旦建出来了，这就是一道裸题。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=*;
const int H=*;
const int INF=;
int head[N+],num,father[N+];
int n;
int hap[N+];
bool prime[H*+];
int T;
struct edge
{
    int u,v;
    int w;
    int next;
    edge(){next=-;}
    bool operator<(const edge& b)const
    {return w<b.w;}
}ed[M<<];
inline void build(int u,int v,int w)
{
    ed[++num].u=u;
    ed[num].v=v;
    ed[num].w=w;
    ed[num].next=head[u];
    head[u]=num;
}
int getfather(int x)  
{
    return father[x]!=x?(father[x]=getfather(father[x])):x;  
}  
inline int unionn(int x,int y)  
{
    return ((x=getfather(x))!=(y=getfather(y)))&&(father[x]=y);  
}
void pri()
{
    prime[]=,prime[]=,prime[]=;
    for(int i=;i<=H;i++)
    if(!prime[])
    {
        for(int j=i+i;j<=H;j+=i)
        prime[j]=;
    }
}  
inline int kruskal()
{
    int ans=;
    int tot=;
    for(int i=;i<=n;++i)
    father[i]=i;
    sort(ed+,ed++num);
    for(int i=;i<=num;++i)
    {
        int u=getfather(ed[i].v),v=getfather(ed[i].u);
        if(u!=v)
        {
            ++tot,ans+=ed[i].w;
            unionn(u,v);
        }
        if(tot==n-)return ans;
    }
    return -;
}
inline int w(int i,int j)
{
    if(!prime[i]||!prime[j]||!prime[i+j])
    return min(min(i,j),abs(i-j));
}
int main()
{
    pri();
    for(scanf("%d",&T);T;T--)
    {
        num=;
        memset(head,-,sizeof(head));
        memset(hap,,sizeof(hap));
        scanf("%d",&n);
        for(int i=;i<=n;i++)
        {
            scanf("%d",&hap[i]);
            for(int j=;j<=i-;j++)
            {
                if(!prime[hap[i]]||!prime[hap[j]]||!prime[hap[i]+hap[j]])
                {
                    build(i,j,w(hap[i],hap[j]));
                    build(j,i,w(hap[i],hap[j]));
                }
            }
        }
        printf("%d\n",kruskal());
    }
    return ;
}