POJ 2349 Arctic Network——最小生成树

你的名字 2022-05-15 09:39 155阅读 0赞

问题来源[Arctic Network][]。  
**Description**  
The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.  
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.  
**Input**  
The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).  
**Output**  
For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.  
**Sample Input**  
1  
2 4  
0 100  
0 300  
0 600  
150 750  
**Sample Output**  
212.13

# 问题描述 #

国防部要在哨所间建立网络以通信，每个哨所都会有一台无线电收发机，部分哨所还会有卫星频道。  
两个哨所优先使用无线电收发机通讯，但有距离限制D，在不超过D的情况下，则可以通过无线电收发机通讯。  
但当两个哨所距离大于D时，则只能通过卫星频道通讯，在两个哨所都有卫星频道的情况下。  
D越高，就要用功率更大的收发机。收发机功率越高，成本也就越高。由于采购与维修考虑，采购的收发机的功率必须一样：也就是说，所有收发机的功率，必须都为需要功率的最大值（即相连哨所对中最大距离D），才能满足要求。

请你确定最小的D值。在每对哨所之间，必须至少有一条通路（直接或者间接）。  
**输入输出**：  
输入第一行给定N，表示测试用例个数。  
每个测试用例的第一行给定S和P，S代表卫星频道数量；P代表哨所数量。  
接下来是P行，每行给出一个哨所的xy坐标。  
**简而言之**：  
有S个卫星和P个哨所，有卫星的哨所对不管距离多大也可以通信。否则，哨所对只有在之间距离小于D的情况才能通信。给定S和P，求D的最小值。

# 试题解析 #

题目要求在每对哨所之间，必须至少有一条通路（直接或者间接），**在不考虑卫星频道的情况下**，则最小生成树就可以完全解决这个问题，因为最小生成树就满足了每个哨所之间有一条直接或间接的通路，且最小生成树也保证了所有哨所对之间的距离之和是最小的，然后将最小生成树中边的权值最大的那个权值作为D返回。  
**然后再考虑卫星频道**，假如把最小生成树中的最大权值的那条边去掉，此时树就会变成两个连通分量。现在原树中第2大的权值就可作为D返回了，这样就找到了更小的D值。同时，只要这两个连通分量中各有一个卫星频道，即总共有两个卫星频道，就可以满足题意（即这两个卫星频道相连形成了一条边连通这两个本不相连的连通分量）。  
**总结分析**：S个卫星频道可以连接起S-1个连通分量（又用了最小生成树思想），即可以去掉最小生成树中前S-1个最大的边，那么第S大的边将作为D返回。注意这里的第几大是指的从大往小排的。

# 代码 #

此代码来自本人博客[最小生成树算法——Kruskal算法、Prim算法、堆优化的Prim算法][Kruskal_Prim_Prim]中的Kruskal算法。按照题目需要，进行了相应的改动。

import math
    
    class Graph:
    
        def __init__(self,S,P,point):
            self.S= S #卫星频道即连通分量个数
            self.V= P #顶点的数量
            # 每个节点的坐标，用其索引来指代每个节点
            self.point = point 
            self.createEdge()
    
        # 生成完全无向图的每条边
        def createEdge(self):
            self.graph = [] #每条边
            for i in range(self.V):
                for j in range(i,self.V):
                    self.graph.append([i,j,self.dis(i,j)])
            #对每条边进行排序
            self.graph = sorted(self.graph,key=lambda item: item[2])        
    
        # 计算两节点间的距离
        def dis(self, i ,j):
            x = self.point[i]
            y = self.point[j]
            result = math.sqrt(sum([pow((a-b),2) for a,b in zip(x,y)]))
            return round(result,2)
    
        # 递归找到每个节点所在子树的根节点
        def find(self, parent, i):
            if parent[i] == i:
                return i
            return self.find(parent, parent[i])
    
        # 联合两颗子树为一颗子树，谁附在谁身上的依据是rank
        def union(self, parent, rank, x, y, xroot, yroot):
    
            #进行路径压缩
            if(xroot != parent[x]):
                parent[x] = xroot
            if(yroot != parent[y]):
                parent[y] = yroot 
    
            if rank[xroot] < rank[yroot]:
                parent[xroot] = yroot
            elif rank[xroot] > rank[yroot]:
                parent[yroot] = xroot
    
            else :
                parent[yroot] = xroot
                rank[xroot] += 1
    
        # 主函数用来构造最小生成树
        def KruskalMST(self):
    
            result =[] #存MST的每条边
    
            i = 0 # 用来遍历原图中的每条边，但一般情况都遍历不完
            e = 0 # 用来判断当前最小生成树的边数是否已经等于V-1
    
            parent = [] ; rank = []
    
            # 创建V个子树，都只包含一个节点
            for node in range(self.V):
                parent.append(node)
                rank.append(0)
    
            # MST的最终边数将为V-1
            while e < self.V -1 :
    
                # 选择权值最小的边，这里已经排好序
                u,v,w =  self.graph[i]
                i = i + 1
                x = self.find(parent, u)
                y = self.find(parent ,v)
    
                # 如果没形成边，则记录下来这条边
                if x != y:
                    #不等于才代表没有环
                    e = e + 1    
                    result.append([u,v,w])
                    self.union(parent, rank, u, v, x, y)      
                # 否则就抛弃这条边
    
            #此时已生成了最小生成树在result
            result = sorted(result, key=lambda item: item[2])
            print(result[-self.S][2])
    
    #因为不是C++或者java，所以写在最外层的就是主函数
    N = eval(input('输入测试用例个数'))
    for i in range(N):
        S,P = map(int,input('输入S P').split())
        point = []#记录每个点
        for j in range(P):
            x,y = map(int,input().split())
            point.append([x,y])
        #为每个用例建立最小生成树
        g = Graph(S,P,point)
        g.KruskalMST()

![这里写图片描述][70]  
与示例输入输出一致。

PS:发现POJ不能提交python代码，**好伤心**ˇ﹏ˇ，可能以后得系统学一遍C++了。虽然phthon很让我爱不释手。

[Arctic Network]: http://poj.org/problem?id=2349
[Kruskal_Prim_Prim]: https://blog.csdn.net/anlian523/article/details/82084154
[70]: /images/20220515/e4cc10cc2ba74ef3844b6b4cefc50de3.png