本文共 2186 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要构建一个最小的树形图，使得所有节点都能收到命令。这个问题可以通过最小生成树算法来解决，特别是使用Kruskal算法来处理有向图中的边。

方法思路

解决代码

import sys
import math
def readints():
    return list(map(int, sys.stdin.readline().split()))
def main():
    n, m = 0, 0
    while True:
        line = sys.stdin.readline()
        if not line:
            break
        n, m = map(int, line.strip().split())
        break
    x = [0.0] * (n + 1)
    y = [0.0] * (n + 1)
    for i in range(1, n+1):
        line = sys.stdin.readline()
        xi, yi = map(float, line.strip().split())
        x[i] = xi
        y[i] = yi
    edges = []
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        dx = x[u] - x[v]
        dy = y[u] - y[v]
        dist = math.hypot(dx, dy)
        edges.append((dist, u, v))
    edges.sort()
    parent = list(range(n+1))
    rank = [1] * (n+1)
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root == v_root:
            return False
        if rank[u_root] < rank[v_root]:
            parent[u_root] = v_root
            rank[v_root] += rank[u_root]
        else:
            parent[v_root] = u_root
            rank[u_root] += v_root
        return True
    total = 0.0
    count = 0
    edges_added = 0
    for dist, u, v in edges:
        if find(u) != find(v):
            union(u, v)
            edges_added += 1
            total += dist
            count += 1
            if count == n:
                break
    if count == n:
        print("{0:.2f}".format(total))
    else:
        print("poor snoopy")
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们能够高效地解决问题，并确保构造的通信网络是最短的。

转载地址：http://qqvo.baihongyu.com/