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

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)