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\$.

Si veda il file MAXFLOW.html per degli esempi e per il formato di input e output richiesto dai problemi.

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 lista G[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.
1. Definire un modulo FORDFULK.py che risolva il problema MASSIMO FLUSSO. Per testare automaticamente la correttezza del proprio codice, invocare
  ./test.sh FORDFULK