OPS > Flussi in una rete

PREMESSA

Sul fianco di una montagna esistono numerose sorgenti.
L’acqua di una sorgente, che si suppone fluire in modo continuo e costante, può scorrere a valle attraverso uno o più canali.
Può avvenire che uno o più canali convergano in un punto in cui esiste una sorgente; in tal caso, la loro acqua si aggiunge a quella fornita dalla sorgente raggiunta.
Questa situazione è descrivibile con un reticolo di nodi (le sorgenti) collegati da archi (i canali).

La situazione quindi è descritta da due tabelle:

  • s(<sorgente>,<litri d’acqua erogata al minuto>), che specifica la quantità d’acqua che sgorga da ogni sorgente (che è un nodo del reticolo),
  • r (<sorgente1>,<sorgente2>), che specifica la presenza di un canale che porta acqua dalla sorgente1 alla sorgente2.

Se da una sorgente escono più canali, l’acqua si divide in parti uguali fra ciascuno di essi.

Nella situazione descritta dal seguente esempio (con radici in a e in b, vedi figura)

  • s(a,6), s(b,5), s(c,1), s(d,4), s(e,3), s(f,2)
  • r(a,c), r(a,d), r(b,d), r(c,e), r(d,e), r(d,f)

la quantità d’acqua che esce dai nodi c, e, f è riportata di seguito

  • c = 4
  • e = 13
  • f = 8

Quesito n. 9 – Olimpiadi di Informatica del 2/12/2010


PROBLEMA

Un reticolo di canali si può descrivere con due tabelle associate ai seguenti due termini:

  • s(<sorgente>,<litri d’acqua erogata al minuto>), che specifica la quantità d’acqua che sgorga da ogni sorgente (che è un nodo del reticolo), e
  • r (<sorgente1>,<sorgente2>), che specifica la presenza di un canale che porta acqua dalla sorgente1 alla sorgente2.

Un reticolo è descritto dalle seguenti due tabelle:

  • s(a,3), s(b,3), s(c,4), s(d,6), s(e,6), s(f,6), s(g,6), s(h,4), s(i,6), s(j,7), s(k,5), s(m,9)
  • r(a,e), r(b,g), r(c,e), r(d,g), r(d,h), r(i,b), r(i,d), r(d,f), r(d,e), r(k,d), r(j,d), r(m,d), r(m,c), r(m,a)

Disegnare il reticolo, evitando incroci tra i rigagnoli, e determinare la quantità di acqua che esce dai nodi e, f, g, h.


Un reticolo di canali è descritto dalle seguenti due tabelle:

  • s(a,3), s(b,6), s(c,6), s(d,2), s(e,1), s(f,10), s(g,3), s(h,4), s(i,1), s(l,3), s(m,1), s(n,10)
  • r(a,d), r(b,d), r(b,e), r(c,e), r(d,g), r(e,g), r(f,i), r(g,i), r(g,l), r(g,m), r(h,m), r(i,n), r(l,n), r(m,n)

Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi d, g, i, n.


Un reticolo di canali è descritto dalle seguenti due tabelle:

  • s(a,8), s(b,4), s(c,2), s(d,6), s(e,4), s(f,10), s(g,1), s(h,1), s(i,10), s(l,2), s(m,2)
  • r(a,b), r(b,c), r(b,d), r(c,e), r(d,e), r(d,f), r(e,g), r(f,g), r(f,h), r(g,h), r(d,i), r(i,f), r(i,l), r(f,l), r(l,h), r(l,m), r(h,m)

Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi d, h, i, m.


Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,4), s(b,2), s(c,8), s(d,4), s(e,1), s(f,2), s(g,2), s(h,2), s(i,10), s(j,5)
  • r(a,c), r(a,d), r(b,d), r(b,e), r(c,d), r(d,e), r(c,f), r(d,f), r(d,g), r(d,h), r(e,h), r(f,i), r(g,f), r(g,i), r(h,g), r(i,j), r(h,j)
Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi d, f, h, j.

Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,5), s(b,5), s(c,1), s(d,3), s(e,1), s(f,4), s(g,1), s(h,4), s(i,2), s(j,4), s(k,6)
  • r(a,b), r(a,c), r(a,d), r(a,e), r(b,c), r(b,f), r(c,f), r(c,d), r(d,f), r(d,g), r(d,e), r(e,g), r(e,h), r(f,h), r(g,h), r(b,h), r(h,i), r(a,h), r(h,j), r(h,k)
Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi d, f, h, k.

Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,2), s(b,1), s(c,3), s(d,3), s(e,5), s(f,1), s(g,2), s(h,1), s(i,2), s(j,1), s(k,1)
  • r(a,b), r(a,c), r(b,d), r(b,e), r(d,e), r(c,e), r(c,f), r(e,f), r(d,g), r(e,g), r(e,h), r(e,i), r(e,j), r(f,j), r(g,h),  r(j,i), r(g,k), r(h,k), r(i,k), r(j,k)
Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi d, e, i, k.

Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,3), s(b,2), s(c,2), s(d,2), s(e,4), s(f,2), s(g,3), s(h,2), s(i,3), s(j,1), s(k,4), s(l,5)
  • r(a,d), r(b,d), r(c,d), r(c,e), r(d,g), r(e,g), r(f,g), r(g,h), r(g,i), r(g,j), r(j,k), r(l,k)

Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi g, h, k.


Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,3), s(b,6), s(c,1), s(d,5), s(e,4), s(f,2), s(g,3)
  • r(a,c), r(f,c), r(c,d), r(c,e), r(c,b), r(e,b), r(b,d), r(b,g)
Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi b, d, g.

Un reticolo di canali è descritto dalle seguenti due tabelle:
  • s(a,4), s(b,8), s(c,2), s(d,2), s(e,4), s(f,1), s(g,3), s(h,1), s(i,2), s(j,1), s(k,2)
  • r(a,d), r(a,k), r(b,d), r(b,e), r(b,f), r(b,g), r(c,g), r(c,k), r(d,h), r(d,i), r(d,j), r(e,h), r(e,i), r(f,i), r(g,f), r(g,i), r(g,j), r(h,i), r(i,j), r(j,k)
Disegnare il reticolo, evitando incroci fra i rigagnoli, e determinare la quantità di acqua che esce dai nodi h, i, g, k.

Una rete di canali è descritta dalle seguenti due tabelle di sorgenti e canali rispettivamente,
  • s(a,2), s(b,4), s(c,4), s(d,2), s(e,2), s(f,4), s(g,2), s(h,3), s(i,3), s(j,3), s(k,3), s(m,1), s(n,1);
  • r(a,e), r(b,f), r(b,e), r(c,f), r(c,g), r(d,g), r(e,h),r(e,i), r(f,i), r(f,j), r(g,j ), r(g,k), r(h,m), r(i,m), r(j,m), r(k,n).
N.B. Si ricordi che una sorgente è descritta dal termine s(<nome della sorgente>,<portata in litri>), un canale è descritto dal termine r(<nome della sorgente a monte>,<nome della sorgente a valle>), e per ogni nodo l’acqua si divide equamente tra canali che escono (a valle) dal nodo.
Disegnare la rete, evitando incroci tra i canali, e determinare la quantità di acqua che esce dai nodi m, n.

Una rete di canali è descritta dalle seguenti due tabelle di sorgenti e canali rispettivamente,
  • s(a,7), s(b,8), s(c,10), s(d,9), s(e,9), s(f,1), s(g,8), s(h,6), s(i,7), s(j,2), s(k,11), s(l,8), s(m,10), s(n,2);
  • r(a,e), r(b,e), r(b,f), r(c,f), r(c,g), r(d,g), r(e,h), r(e,i), r(f,i), r(f,j), r(g,j), r(g,k), r(h,l), r(i,l), r(i,m), r(j,m), r(j,n), r(k,n).
N.B. Si ricordi che una sorgente è descritta dal termine s(<nome della sorgente>,<portata in litri>), un canale è descritto dal termine r(<nome della sorgente a monte>,<nome della sorgente a valle>), e per ogni nodo l’acqua si divide equamente tra canali che escono (a valle) dal nodo.
Disegnare la rete, evitando incroci tra i canali, e determinare da quale nodo finale esce la quantità maggiore di acqua.
N.B. Un nodo è finale quando non compare come primo argomento in un termine “r”: cioè quando non ha successori (a valle).