C - 畅通工程再续

喜欢ヅ旅行 2022-03-19 08:52 190阅读 0赞

### 题目描述： ###

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。  
Input  
输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。  
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。  
Output  
每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.  
Sample Input  
2  
2  
10 10  
20 20  
3  
1 1  
2 2  
1000 1000  
Sample Output  
1414.2  
oh!

##### 分析： #####

本题的话其实也算是一个模板题吧。重点是将所输入的下标转化成邻接矩阵。根据邻接矩阵的定义，我们可以用一个嵌套循环来转化为邻接矩阵。同时，在转化的过程中我们就可以将不满足的情况给去掉（即：<10||>1000的）。

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
       using namespace std;
    #define INF 1000000
    void MinSpanTree(double Graph[][111],int n)
    {
        int i,j,k;
        int vexs[111];
        double weight[111];
        double sum=0;
        int mark=1;
        for(int i=0;i<n;i++)
        {
            vexs[i]=i;
            weight[i]=Graph[0][i];
        }
        for(i=0;i<n-1;i++)
        {
            double Min=INF;
            j=0;
            k=0;
            while(j<n)
            {
                if(weight[j]&&Min>weight[j])
                {
                    k=j;
                    Min=weight[j];
                }
              j++;
            }
            sum+=Min;
            for(j=0;j<n;j++)
            {
                if(weight[j]&&weight[j]>Graph[k][j])
                {
                    vexs[j]=k;
                    weight[j]=Graph[k][j];
                }
            }
        }
      if(sum>=INF)//最后特判一下。
         printf("oh!\n");
      else
        printf("%0.1lf\n",sum*100);
    }
    int main()
    {
        double Graph[111][111];
        int coord[111][2];
        int T,n;
        while(~scanf("%d",&T))
        {
            while(T--)
            {
                scanf("%d",&n);
                for(int i=0;i<n;i++)
                    scanf("%d%d",&coord[i][0],&coord[i][1]);
                for(int i=0;i<n;i++)
                    for(int j=0;j<n;j++)
                        {
                            double distance=sqrt((coord[i][0]-(double)coord[j][0])*(coord[i][0]-coord[j][0])+((double)coord[i][1]-coord[j][1])*(coord[i][1]-coord[j][1]));
                            if(distance>=10&&distance<=1000)
                                Graph[i][j]=distance;
                            else
                                Graph[i][j]=INF;
                            if(i==j)
                                Graph[i][j]=0;
                        }
                MinSpanTree(Graph,n);
            }
        }
    
    }