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"> 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>