Sto cercando di capire come utilizzare l'algoritmo Ford Fulkerson in questa situazione La situazione è simile a sudoku. Abbiamo una matrice a
che contiene valori interi. L'ultima colonna di ogni riga e ultima riga di ogni colonna, contiene la somma dell'intera riga/colonna.Flusso massimo nel grafico bipartito utilizzando Ford Fulkerson per determinare i valori sufficienti per sommare
Esempio:
int[][] a = {{1, 3, 5, 9},
{4, 2, 1, 7},
{5, 5, 6, *}} // * Is not determined since the sums
// * do not count as summable values.
Questo fatto è che i valori all'interno della matrice non sono sempre corrette. I valori per la somma non sempre corretta, ad esempio:
int[][] a = {{1, 3, 3, 9},
{2, 3, 1, 7},
{5, 5, 6, *}} // * Is not determined since the sums do
// * not count as summable values.
C'è una matrice b
che contiene la differenza max una cella può avere per soddisfare la somma proposta. Ad esempio
int[][] b = {{1, 0, 3},
{2, 1, 2}}
Ad esempio per il valore di a[0][0]
, che è 1, le differenze max è il valore in b[0][0]
, che è 1, quindi il valore a[0][0]
può essere modificato a 0 o 2 massimo (e tutti i numeri in mezzo, ma per questo esempio abbiamo solo 2 opzioni).
La mia domanda è: data una matrice a
(con valori non validi per una determinata somma) e una matrice b
con le differenze massime che possono essere utilizzate per soddisfare la somma richiesta, come posso determinare se è possibile anche con la data le differenze massime e come ottengo un risultato valido di tale matrice (se così esiste).
mio approccio attuale (che non funziona):
- Fare un grafo bipartito delle righe e delle colonne, in modo da avere una fonte, un lavandino e un nodo per ogni riga e colonna.
- Quindi collegare ogni riga a ciascuna colonna.
- Quindi collegare la sorgente a ciascuna riga.
- Quindi collegare ciascuna colonna al lavandino.
- Impostare le capacità per i bordi dalla sorgente a ciascun nodo di riga su Math.Abs (somma corrente di numeri in
a
- data somma di numeri ina
(per quella riga)). - Uguale per i bordi da ogni nodo della colonna al sink (ma per la colonna questa volta si somma).
- Impostare le capacità tra i nodi per le righe sulle colonne alle differenze massime indicate in
b
di conseguenza per ciascuna cella. - Utilizzare Ford Fulkerson per determinare il flusso massimo.
non so come dovrei usare i miei risultati del algoritmo per determinare i valori corretti per matrice a
per soddisfare la somma data per ogni riga e colonna.
@Smandoli Grazie, ho modificato i tag. – Robinhopok
Chiunque può aiutarmi? – Robinhopok
è la differenza massima o la differenza massima assoluta? – norisknofun