0616 - Zapada

Cerința

Orașul Kruskal are n intersecții unite prin m străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Maleficul Costel îl forțează pe Gigel să deszăpezească anumite străzi, din motive doar de el știute. Ajutați-l pe Gigel să determine costul minim pentru deszăpezirea orașului, astfel încât să fie deszăpezite străzile dorite de Costel și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Date de intrare

Fișierul de intrare zapada.in conține pe prima linie numerele n m, iar pe următoarele m linii câte un triplet i j c, cu semnificația: există stradă între intersecțiile i j și are costul deszăpezirii egal cu c. Urmează o linie care conține numărul k de străzi pe care Costel le dorește deszăpezite, iar următoarea linie conține k numere distincte între 1 și m, reprezentând numărul de ordine al străzilor care vor fi obligatoriu deszăpezite.

Date de ieșire

Fișierul de ieșire zapada.out va conține pe prima linie costul total minim al deszăpezirii orașului, în condițiile precizate.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ k < m ≤ n*(n-1)/2
• costurile deszăpezirii străzilor sunt numere naturale nenule cel mult egale cu 1000
• numerele celor k străzi care trebuie deszăpezite sunt dintre numerele de ordine ale celor m străzi date

Exemplu:

zapada.in

7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
2
2 11

zapada.out

15

Explicație

Alături de străzile 1-7 și 6-7 care trebuie obligatoriu deszăpezite, se mai deszăpezesc străzile: 1-2, 2-5, 4-5 și 3-4. Costul total al deszăpezirii acestor străzi este 4+5+2+2+1+1=15

Rezolvare

<syntaxhighlight lang="python3"> class Muchie:

   def __init__(self, nod1, nod2, cost):
       self.nod1 = nod1
       self.nod2 = nod2
       self.cost = cost

def cmp(a, b):

   return a.cost < b.cost

def radacina(a, t):

   r = a
   while t[r] != r:
       r = t[r]
   while t[a] != a:
       b = t[a]
       t[a] = r
       a = b
   return r

def main():

   with open("zapada.in", 'r') as f:
       n, m = map(int, f.readline().split())
       v = [None] * (m + 1)
       for i in range(1, m + 1):
           nod1, nod2, cost = map(int, f.readline().split())
           v[i] = Muchie(nod1, nod2, cost)  # Am adăugat crearea obiectului de tip Muchie
       t = list(range(n + 1))

       k = int(f.readline())
       strazi_dorite = list(map(int, f.readline().split()))  # Citim lista de străzi dorite
       sum = 0
       for x in strazi_dorite:  # Iterăm prin străzile dorite și adăugăm costurile lor
           sum += v[x].cost
           v[x].cost = 0

       v = v[1:]  # Skip the first element which is None
       v.sort(key=lambda x: x.cost)

       nr_arb = 1
       for i in range(len(v)):
           if nr_arb >= n:
               break
           r1 = radacina(v[i].nod1, t)
           r2 = radacina(v[i].nod2, t)
           if r1 == r2:
               continue
           t[r2] = r1
           sum += v[i].cost
           nr_arb += 1

   with open("zapada.out", 'w') as f:
       f.write(str(sum))

if __name__ == "__main__":

   main()

</syntaxhighlight>