【POJ 2349】Arctic Network（Kruskal算法）

Dear 丶 2022-02-17 15:13 152阅读 0赞

题目链接：[http://poj.org/problem?id=2349][http_poj.org_problem_id_2349]

题意：

有S颗卫星和P个哨所，有卫星的两个哨所之间可以任意通信；否则，一个哨所只能和距离它小于等于D的哨所通信。给出卫星的数量和P个哨所的坐标，求D的最小值。

思路：

这道题主要要明白题意，本来就是个英文题，再加上有点儿绕，实在是在难为我这个英文小白，所以看懂英语真的很重要鸭。。。。

题上说一个卫星频道可以使两个哨所任意通信而忽略他们之间的距离，否则两个哨所之间只能通过电台进行通信，并且两个哨所之间的距离不能超过D，不然不在电台所能触及的范围之内就不能通信，距离D取决于电台的力量；给出卫星个数S，哨所个数P，以及每个哨所所在的坐标，问电台所需要的最小的距离D。

S个卫星可以去掉S-1个哨所，所以最后只需要连接P-S+1各哨所就可以了，所以用Kruskal算法把所有边进行排序，最后输出第P-S条边的距离即电台所需要的最小的距离，就可以使剩下的哨所都能通过此电台通信。

（还有这道题在POJ上提交时如果你选的是G++提交，输出必须用%f，用%lf提交会答案错误，详细原因[请点击这里][Link 1]）

My Code：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    int fa[505],n,cunt,m;
    struct island
    {
        double x,y;
    }s[505];
    struct Island
    {
        int s,e;
        double dis;
    }c[150000];
    int cmp(Island c1,Island c2)
    {
        return c1.dis < c2.dis;
    }
    int father(int x)
    {
        if(x == fa[x]) return x;
        else
        {
            int root = father(fa[x]);
            fa[x] = root;
            return root;
        }
    }
    double Kruskal()
    {
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        sort(c,c+cunt,cmp);
        int ans = 0;
        double sum ;
        for(int i = 0; i < cunt; i++)
        {
            int a = father(c[i].s);
            int b = father(c[i].e);
            if(a != b)
            {
                ans++;
                fa[a] = b;
                if(ans == n-m)///输出第P-S条边
                {
                    sum = c[i].dis;
                    break;
                }
            }
        }
        return sum;
    }
    double distance(double x0,double y0,double x1,double y1)
    {
        return sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
    }
    int main()
    {
        int t;
        cin >> t;
        while(t--)
        {
            scanf("%d%d",&m,&n);
            for(int i = 1; i <= n; i++)
                cin >> s[i].x >> s[i].y;
            cunt = 0;
            for(int i = 1; i < n; i++)
            {
                for(int j = i+1; j <= n; j++)
                {
                    c[cunt].dis = distance(s[i].x,s[i].y,s[j].x,s[j].y);
                    c[cunt].s = i;
                    c[cunt].e = j;
                    cunt++;
                }
            }
            double sum = Kruskal();
            printf("%.2f\n",sum);
        }
    
        return 0;
    }

[http_poj.org_problem_id_2349]: http://poj.org/problem?id=2349
[Link 1]: https://blog.csdn.net/qq_41181772/article/details/89407683