irachex · February 9, 2014 09:26 · Feb 9, 2014
diff --git a/minimum_spanning_tree.py b/minimum_spanning_tree.py
@@ -0,0 +1,90 @@
+"""
+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()