Tree

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2877 Accepted Submission(s): 883

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define ios() ios::sync_with_stdio(false)

#define INF 0x3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

int g[][];

int vis[],n;

int dis[],x,y,z;

int val[],t;

int ans[];

void get_prime()

{

    memset(ans,,sizeof(ans));

    ans[]=;

    for(int i=;i<;i++)

    {

        if(ans[i]) continue;

        for(int j=;j*i<;j++)

        {

            ans[j*i]=;

        }

    }

}

void init()

{

    for(int i=;i<=n;i++)

    {

        for(int j=;j<i;j++)

        {

            g[i][j]=g[j][i]=INF;

        }

        g[i][i]=;

    }

}

int prime()

{

    for(int i=;i<=n;i++)

    {

        dis[i]=g[][i];

        vis[i]=;

    }

    vis[]=;

    int minn,v=,sum=;

    for(int i=;i<n;i++)

    {

        minn=INF;

        for(int j=;j<=n;j++)

        {

            if(!vis[j] && minn>dis[j])

            {

                minn=dis[j];

                v=j;

            }

        }

        if(minn==INF) return -;

        vis[v]=;

        sum+=minn;

        for(int j=;j<=n;j++)

        {

            if(!vis[j]) dis[j]=min(dis[j],g[v][j]);

        }

    }

    return sum;

}

int main()

{

    get_prime();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        init();

        for(int i=;i<=n;i++)

        {

            scanf("%d",&val[i]);

            for(int j=;j<=i;j++)

            {

                if(!ans[val[i]] || !ans[val[j]] || !ans[val[i]+val[j]])

                    g[i][j]=g[j][i]=min(g[i][j],min(min(val[i],val[j]),abs(val[i]-val[j])));

            }

        }

        printf("%d\n",prime());

    }

    return ;

}

Sample Output

4
-1

必须保证va 或者 vb 或者 va+vb是素数

巴特西

HDU 2689 Tree

Tree

最新文章

热门文章