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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

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>