4155 - Harta3

Cerința

Harta unei regiuni este reprezentată într-un sistem de coordonate cartezian și sunt cunoscute coordonatele a n orașe, numerotate de la 1 la n.

Se dorește construirea unor drumuri bidirecționale între anumite perechi de orașe, astfel încât:

• să se poate ajunge din orice oraș în oricare altul folosind unul sau mai multe dintre drumurile construite;
• suma lungimilor drumurilor construite să fie minimă.

Să se determine suma lungimilor drumurilor construite.

Date de intrare

Fișierul de intrare harta3.in conține pe prima linie numărul de orașe n, iar pe fiecare dintre următoarele n linii câte două numere întregi x y, reprezentând coordonatele acestora.

Date de ieșire

Fișierul de ieșire harta3.out va conține pe prima linie suma lungimilor drumurilor construite, cu cel puțin trei zecimale exacte.

Restricții și precizări

• 1 ≤ n ≤ 100;
• coordonatele orașelor sunt din intervalul [-200, 200];
• lungimea drumului dintre două orașe se determină cu formula , unde  și  sunt coordonatele acestora.

Exemplu:

harta3.in

4
1 2
2 -1
6 5
4 2

harta3.out

9.7678

Rezolvare

<syntaxhighlight lang="python3"> import math

class Muchie:

   def __init__(self, i, j, cost):
       self.i = i
       self.j = j
       self.cost = cost

def find(P, i):

   if P[i] == i:
       return i
   else:
       P[i] = find(P, P[i])
       return P[i]

def union(P, rank, x, y):

   root_x = find(P, x)
   root_y = find(P, y)
   if root_x != root_y:
       if rank[root_x] > rank[root_y]:
           P[root_y] = root_x
       elif rank[root_x] < rank[root_y]:
           P[root_x] = root_y
       else:
           P[root_y] = root_x
           rank[root_x] += 1

def main():

   with open("harta3.in", "r") as fin:
       n = int(fin.readline().strip())
       x = [0] * (n + 1)
       y = [0] * (n + 1)
       for i in range(1, n + 1):
           x[i], y[i] = map(int, fin.readline().strip().split())

   M = []
   for i in range(1, n):
       for j in range(i + 1, n + 1):
           cost = math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
           M.append(Muchie(i, j, cost))
   
   M.sort(key=lambda muchie: muchie.cost)

   P = [i for i in range(n + 1)]
   rank = [0] * (n + 1)
   S = 0.0

   for muchie in M:
       if find(P, muchie.i) != find(P, muchie.j):
           union(P, rank, muchie.i, muchie.j)
           S += muchie.cost
   
   with open("harta3.out", "w") as fout:
       fout.write(f"{S:.4f}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>