Problem:


Problem C:  Save your cats

Nicholas Y. Alford was a cat lover. He had a garden in a village and kept many cats in his garden. The cats were so cute that people in the village also loved them.

One day, an evil witch visited the village. She envied the cats for being loved by everyone. She drove magical piles in his garden and enclosed the cats with magical fences running between the piles. She said “Your cats are shut away in the fences until they become ugly old cats.” like a curse and went away.

Nicholas tried to break the fences with a hummer, but the fences are impregnable against his effort. He went to a church and asked a priest help. The priest looked for how to destroy the magical fences in books and found they could be destroyed by holy water. The Required amount of the holy water to destroy a fence was proportional to the length of the fence. The holy water was, however, fairly expensive. So he decided to buy exactly the minimum amount of the holy water required to save all his cats. How much holy water would be required?

Input

The input has the following format:

N M

x1 y1

.

.

.

xN yN

p1 q1

.

.

.

pM qM

The first line of the input contains two integers N (2 ≤ N ≤ 10000) and M (1 ≤ M). N indicates the number of magical piles and M indicates the number of magical fences. The following N lines describe the coordinates of the piles. Each line contains two integers xi and yi (-10000 ≤ xi, yi ≤ 10000). The following M lines describe the both ends of the fences. Each line contains two integers pj and qj (1 ≤ pj, qj ≤ N). It indicates a fence runs between the pj-th pile and the qj-th pile.

You can assume the following:

 No Piles have the same coordinates.

 A pile doesn’t lie on the middle of fence.

 No Fences cross each other.

 There is at least one cat in each enclosed area.

 It is impossible to destroy a fence partially.

 A unit of holy water is required to destroy a unit length of magical fence.

Output

Output a line containing the minimum amount of the holy water required to save all his cats. Your program may output an arbitrary number of digits after the decimal point. However, the absolute error should be 0.001 or less.

Sample Input 1

3 3
0 0
3 0
0 4
1 2
2 3
3 1

Output for the Sample Input 1

3.000

Sample Input 2

4 3
0 0
-100 0
100 0
0 100
1 2
1 3
1 4

Output for the Sample Input 2

0.000

Sample Input 3

6 7
2 0
6 0
8 2
6 3
0 5
1 7
1 2
2 3
3 4
4 1
5 1
5 4
5 6

Output for the Sample Input 3

7.236

Sample Input 4

6 6
0 0
0 1
1 0
30 0
0 40
30 40
1 2
2 3
3 1
4 5
5 6
6 4

Output for the Sample Input 4

31.000



Sample input:
3 3
0 0
3 0
0 4
1 2
2 3
3 1


Sample output:
3.000

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().rstrip().split())
pileDict = {}
for i in range(N):
    prow,pcol = map(lambda x: int(x),input().rstrip().split())
    pileDict[i] = [prow,pcol]
edgeDict = {}
for i in range(M):
    fs,fe = map(lambda x: int(x),input().rstrip().split())
    edgeDict[i] = [fs,fe]


print("test")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size
    
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            if self.table[x_root] < self.table[y_root]:
                self.table[x_root] += self.table[y_root]
                self.table[y_root] = x_root
            else:
                self.table[y_root] += self.table[x_root]
                self.table[x_root] = y_root
    
    def isDisjoint(self, x, y):
        return self.find(x) != self.find(y)

def solve():
    import sys
    file_input = sys.stdin
    N, M = map(int, file_input.readline().split())
    
    piles = [tuple(map(int, file_input.readline().split())) for i in range(N)]
    
    fences = []
    for i in range(M):
        p, q = map(int, file_input.readline().split())
        p -= 1
        q -= 1
        px, py = piles[p]
        qx, qy = piles[q]
        fence_len = ((px - qx) ** 2 + (py - qy) ** 2) ** 0.5
        fences.append((fence_len, p, q))
    
    fences.sort(reverse=True)
    S = UnionFind(N)
    fences_len = 0
    
    for f_len, p1, p2 in fences:
        if S.isDisjoint(p1, p2):
            S.union(p1, p2)
        else:
            fences_len += f_len
    
    print(fences_len)

solve()

Submission status: Accepted

Solution code:
def dist(c1, c2):
    return ((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)**.5


def kruskal(edges, size):
    uf = UnionFind(size)
    edges = sorted(edges, key=lambda e: e[2])[::-1]
    ret = 0
    for u, v, weight in edges:
        if not uf.same(u, v):
            uf.unite(u, v)
            ret += weight
    return ret


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
coords = [tuple(map(int, input().split())) for i in range(N)]
edges = []
for i in range(M):
    p, q = map(lambda x: int(x) - 1, input().split())
    edges.append((p, q, dist(coords[p], coords[q])))
print(sum(e[2] for e in edges) - kruskal(edges, N))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]

    def root(self,x):
        if self.data[x]<0:
            return x
        else:
            self.data[x]=self.root(self.data[x])
            return self.data[x]

    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x

    def same(self,x,y):
        return self.root(x)==self.root(y)

    def size(self,x):
        return -self.data[self.root(x)]


n,m=map(int,input().split())
uf=UnionFind(n)
cd=[]
g=[[] for i in range(n)]
sm=0.0
for i in range(n):
    cd.append(tuple(map(int,input().split())))
f=0
for j in range(m):
    p,q=map(int,input().split())
    p,q=p-1,q-1
    uf.uni(p,q)
    f=p
    g[p].append((-((cd[p][0]-cd[q][0])**2+(cd[p][1]-cd[q][1])**2)**0.50,q))
    g[q].append((-((cd[p][0]-cd[q][0])**2+(cd[p][1]-cd[q][1])**2)**0.50,p))
    sm+=((cd[p][0]-cd[q][0])**2+(cd[p][1]-cd[q][1])**2)**0.50

from heapq import heappush, heappop, heapify
used = [0 for i in range(n)]
ans = 0
for i in range(n):
    if uf.data[i]>=0:
        continue
    que = [(c, w) for c, w in g[i]]
    used[i] = 1
    heapify(que)
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = 1
        ans -= cv
        for c, w in g[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

print(sm-ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def ky2(a,b):
    return pow(a[0]-b[0], 2) + pow(a[1]-b[1], 2)

def main():
    rr = []

    def f(n,m):
        global fr
        a = [LI() for _ in range(n)]
        es = []
        for _ in range(m):
            b,c = LI_()
            es.append([ky2(a[b],a[c]), b, c])
        es.sort(reverse=True)
        r = 0
        uf = UnionFind(n)
        for k,b,c in es:
            if uf.union(b,c):
                continue
            r += pow(k,0.5)

        return '{:0.3f}'.format(r)

    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m))
        break
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())