1651 - Graf: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: = 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 <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</co...)
 
Fără descriere a modificării
 
(Nu s-a afișat o versiune intermediară efectuată de același utilizator)
Linia 6: Linia 6:


= Date de ieșire =
= Date de ieșire =
Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.
Programul va afișa pe ecran numărul <code>vf</code>, 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 =
= Restricții și precizări =
Linia 45: Linia 45:
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, m, muchii):
from typing import List, Tuple
    # 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):
def check_constraints(n, m, edges):
     if not (1 <= n <= 100):
         return False
         return False
    for edge in edges:
        i, j, p = edge
        if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
            return False
     return True
     return True


def gaseste_varf_minim_media_ponderilor(n, m, muchii):
def main():
     # Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf
     nMAX = 100
     ponderi_vf = {i: [] for i in range(1, n + 1)}
     mat = [[] for _ in range(nMAX + 1)]  # mat[i][0] = (j, p) (edge between i and j with weight p)
 
    n, m = map(int, input().split())
 
    if not (1 <= n <= 100):
        print("Detele nu respecta restrictiile impuse")
        return


     # Citim și memorăm ponderile muchiilor în dicționar
     edges = [tuple(map(int, input().split())) for _ in range(m)]
    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
     if not check_constraints(n, m, edges):
    medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()}
        print("Detele nu respecta restrictiile impuse")
        return


     # Găsim vârful cu media minimă
     for i, j, p in edges:
    vf_min_media = min(medii_ponderi, key=medii_ponderi.get)
        mat[i].append((j, p))
        mat[j].append((i, p))


     return vf_min_media
     vfmin = 0
    medmin = float('inf')


# Citirea numărului de vârfuri
    for i in range(1, n + 1):
n = int(input("Introduceți numărul de vârfuri "))
        _sum = sum(weight for _, weight in mat[i])
if not (1 <= n <= 100):
        if _sum / len(mat[i]) < medmin:
    print("Datele nu corespund restrictiilor impuse")
            medmin = _sum / len(mat[i])
else:
            vfmin = i
    # Citirea numărului de muchii
    m = int(input("Introduceți numărul de muchii: "))


    # Citirea muchiilor și ponderilor
     print(vfmin)
     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
if __name__ == "__main__":
    rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii)
     main()
     if rezultat is not None:
        print(rezultat)


</syntaxhighlight>
</syntaxhighlight>

Versiunea curentă din 7 ianuarie 2024 13:07

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

from typing import List, Tuple

def check_constraints(n, m, edges):
    if not (1 <= n <= 100):
        return False
    for edge in edges:
        i, j, p = edge
        if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
            return False
    return True

def main():
    nMAX = 100
    mat = [[] for _ in range(nMAX + 1)]  # mat[i][0] = (j, p) (edge between i and j with weight p)

    n, m = map(int, input().split())

    if not (1 <= n <= 100):
        print("Detele nu respecta restrictiile impuse")
        return

    edges = [tuple(map(int, input().split())) for _ in range(m)]

    if not check_constraints(n, m, edges):
        print("Detele nu respecta restrictiile impuse")
        return

    for i, j, p in edges:
        mat[i].append((j, p))
        mat[j].append((i, p))

    vfmin = 0
    medmin = float('inf')

    for i in range(1, n + 1):
        _sum = sum(weight for _, weight in mat[i])
        if _sum / len(mat[i]) < medmin:
            medmin = _sum / len(mat[i])
            vfmin = i

    print(vfmin)

if __name__ == "__main__":
    main()
Adus de la „http://wiki.universitas.ro/index.php?title=1651_-_Graf&oldid=9181”