1651 - Graf

Cerința

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Date de intrare

Programul citește de la tastatură numerele n m, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi m triplete i j p, reprezentând muchiile, date prin extremități și pondere.

Date de ieșire

Programul va afișa pe ecran numărul vf, reprezentând vârful determinat.

Restricții și precizări

• 1 ≤ n ≤ 100
• ponderile muchiilor sunt numere naturale nenule mai mici decât 1000
• graful dat nu conține noduri izolate

Exemplul 1:

Intrare

5 6
1 2 10
2 3 2
2 5 2
3 5 12
3 4 1
4 5 5

Ieșire

4

Explicație

Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

• pentru vârful 1 media este 10
• pentru vârful 2 media este 4.66667
• pentru vârful 3 media este 5
• pentru vârful 4 media este 3
• pentru vârful 5 media este 6.33333

Astfel media minimă este 3, pentru vârful 4

Exemplul 2:

Intrare

101

consola

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restricții(n, m, muchii):

   # Verificăm restricțiile
   if not (1 <= n <= 100) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii):
       return False
   return True

def gaseste_varf_minim_media_ponderilor(n, m, muchii):

   # Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf
   ponderi_vf = {i: [] for i in range(1, n + 1)}

   # Citim și memorăm ponderile muchiilor în dicționar
   for i in range(m):
       vf1, vf2, pondera = muchii[i]
       ponderi_vf[vf1].append(pondera)
       ponderi_vf[vf2].append(pondera)

   # Calculăm media aritmetică a ponderilor pentru fiecare vârf
   medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()}

   # Găsim vârful cu media minimă
   vf_min_media = min(medii_ponderi, key=medii_ponderi.get)

   return vf_min_media

1. Citirea numărului de vârfuri

n = int(input("Introduceți numărul de vârfuri ")) if not (1 <= n <= 100):

   print("Datele nu corespund restrictiilor impuse")

else:

   # Citirea numărului de muchii
   m = int(input("Introduceți numărul de muchii: "))

   # Citirea muchiilor și ponderilor
   print("Introduceți extremitățile și ponderea fiecărei muchii:")
   muchii = [tuple(map(int, input().split())) for _ in range(m)]

   # Apelarea funcției și afișarea rezultatului
   rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii)
   if rezultat is not None:
       print(rezultat)

</syntaxhighlight>