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 este10
- pentru vârful
2
media este4.66667
- pentru vârful
3
media este5
- pentru vârful
4
media este3
- pentru vârful
5
media este6.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
- 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>