minimum_spanning_tree.py

"""
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=203
"""

import math


def prim(n, edges):
    g = [[] for i in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))

    d = [float('inf') for i in range(n)]
    b = [False for i in range(n)]
    d[0] = 0
    ans = 0

    for i in range(n):
        min_dist = float('inf')
        k = 0
        for j in range(n):
            if not b[j] and min_dist > d[j]:
                min_dist = d[j]
                k = j

        b[k] = True
        ans += min_dist

        for j, w in g[k]:
            if not b[j] and d[j] > w:
                d[j] = w

    return ans


def kruskal(n, edges):
    a = [i for i in range(n)]

    def ancestor(i):
        if a[i] == i:
            return i
        a[i] = ancestor(a[i])
        return a[i]

    ans = 0
    edges = sorted(edges, key=lambda (u, v, w): w)
    tree = []
    for u, v, w in edges:
        if ancestor(u) != ancestor(v):
            a[ancestor(u)] = ancestor(v)
            ans += w
            tree.append((u, v, w))
            if len(tree) == n - 1:
                break

    return ans


def main():
    testcase = 0
    while True:
        n = int(raw_input())
        if n == 0:
            return

        a = []
        for i in range(n):
            x, y = map(float, raw_input().split())
            a.append((x, y))

        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                xi, yi = a[i]
                xj, yj = a[j]
                w = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
                edges.append((i, j, w))

        #ans = prim(n, edges)
        ans = kruskal(n, edges)

        testcase += 1
        if testcase > 1:
            print
        print "Case #%s:" % testcase
        print "The minimal distance is: %.2f" % ans


main()