Vizualizare sursă pentru „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 <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</code>, reprezentând muchiile, date prin extremități și pondere.

= Date de ieșire =
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 =

* <code>1 ≤ n ≤ 100</code>
* ponderile muchiilor sunt numere naturale nenule mai mici decât <code>1000</code>
* 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 <code>1</code> media este <code>10</code>
* pentru vârful <code>2</code> media este <code>4.66667</code>
* pentru vârful <code>3</code> media este <code>5</code>
* pentru vârful <code>4</code> media este <code>3</code>
* pentru vârful <code>5</code> media este <code>6.33333</code>

Astfel media minimă este <code>3</code>, pentru vârful <code>4</code>

== Exemplul 2: ==
<code>Intrare</code>
 <code>101</code>
<code>consola</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>