Esercizio: Reti di flusso e algoritmo Ford-Fulkerson
Questo esercizio riguarda il seguente problema.
Dati: una rete capacitata su \$n\$ nodi.
Trova: un flusso di valore massimo dal nodo 1 al nodo \$n\$.
Formato di input/output
Si veda il file MAXFLOW.html per degli esempi e per il formato di input e output richiesto dai problemi.
Istruzioni
La classe flow_network
definita in FLOWNET.py
è un tipo di dato che consente di rappresentare una rete capacitata G:
-
G = flow_network(n)
crea una rete capacitata G con n nodi, numerati da 0 a n-1, e nessun arco. -
G.add_arc(u, v, cap)
aggiunge a G un arco orientato di capacitàcap
dal nodo u al nodo v, e un corrispondente arco rovescio da v ad u di capacità 0. -
Per ogni nodo u,
G[u]
è la lista degli archi uscenti da u. -
e.tail
è il nodo di partenza dell’arco e. -
e.head
è il nodo di arrivo dell’arco e. -
e.cap
è la capacità dell’arco e. -
e.rev
è l’indice dell’arco rovescio di e nella listaG[e.head]
(dato un arco, permette di identificare rapidamente il suo arco rovescio). -
e.f
è una variabile utilizzabile da un algoritmo per indicare il flusso sull’arco e.-
Definire un modulo
FORDFULK.py
che risolva il problema MASSIMO FLUSSO. Per testare automaticamente la correttezza del proprio codice, invocare./test.sh FORDFULK
-