畅通工程再续

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21693 Accepted Submission(s): 6856

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

Input

输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output

每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.

Sample Input

10 10

20 20

1 1

2 2

1000 1000

Sample Output

1414.2

oh!

思路：首先利用并查集判断所有坐标是否能构成一个连通图。若是一个连通图则直接求最小生成树。

#include<cstdio>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

const int MAXN=;

const double INF=1.0e9;

typedef pair<double,int> P;

struct Point{

    int x,y;

}ps[MAXN];

int V;

vector<int> G[MAXN];

double mp[MAXN][MAXN];

int par[MAXN];

int rnk[MAXN];

double dist(int x1,int y1,int x2,int y2)

{

    return sqrt(double((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));

}

void prep(int n)

{

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

    {

        par[i]=i;

        rnk[i]=;

    }

}

int fnd(int x)

{

    if(par[x]==x)

        return x;

    return par[x]=fnd(par[x]);

}

void unite(int x,int y)

{

    int a=fnd(x);

    int b=fnd(y);

    if(a==b)

    {

        return ;

    }

    if(rnk[a]<rnk[b])

    {

        par[a]=b;

    }

    else

    {

        par[b]=a;

        if(rnk[a]==rnk[b])    rnk[a]++;

    }

}

bool judge(int n)

{

    int f=fnd();

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

        if(f!=par[i])    return false;

    return true;

}

double d[MAXN];

int vis[MAXN];

double prim(int s)

{

    double ans=;

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

    {

        d[i]=INF;

        vis[i]=;

    }

    d[s]=;

    priority_queue<P,vector<P>,greater<P> > que;

    que.push(P(,s));

    while(!que.empty())

    {

        P now=que.top();que.pop();

        int v=now.second;

        if(vis[v])    continue;

        ans+=now.first;

        vis[v]=;

        for(int i=;i<G[v].size();i++)

        {

            int to=G[v][i];

            if(d[to]>mp[v][to])

            {

                d[to]=mp[v][to];

                que.push(P(d[to],to));

            }

        }

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&V);

        prep(V);

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

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

                if(i==j)    mp[i][j]=;

                else mp[i][j]=INF;

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

        {

            scanf("%d%d",&ps[i].x,&ps[i].y);

        }

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

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

            {

                double co=dist(ps[i].x,ps[i].y,ps[j].x,ps[j].y);

                if(co<||co>)    continue;

                mp[i][j]=mp[j][i]=co;

                G[i].push_back(j);

                G[j].push_back(i);

                unite(i,j);

            }

        if(judge(V))

        {

            double ans=prim();

            printf("%0.1lf\n",ans*);

        }

        else

        {

            printf("oh!\n");

        }

    }

    return ;

}

巴特西

HDU1875(最小生成树)

畅通工程再续

最新文章

热门文章