Danciu: Pagină nouă: = 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 de...

2024-06-04T01:26:30Z

Pagină nouă: = Cerința = Orașul Kruskal are <code>n</code> intersecții unite prin <code>m</code> 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 de...

New page

= Cerința =
Orașul Kruskal are <code>n</code> intersecții unite prin <code>m</code> 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 <code>zapada.in</code> conține pe prima linie numerele <code>n m</code>, iar pe următoarele <code>m</code> linii câte un triplet <code>i j c</code>, cu semnificația: există stradă între intersecțiile <code>i j</code> și are costul deszăpezirii egal cu <code>c</code>. Urmează o linie care conține numărul <code>k</code> de străzi pe care Costel le dorește deszăpezite, iar următoarea linie conține <code>k</code> numere distincte între <code>1</code> și <code>m</code>, reprezentând numărul de ordine al străzilor care vor fi obligatoriu deszăpezite.

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

= Restricții și precizări =

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

= Exemplu: =
<code>zapada.in</code>
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
<code>zapada.out</code>
15

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

== 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>

0616 - Zapada - Revision history