Flusso massimo nel grafico bipartito utilizzando Ford Fulkerson per determinare i valori sufficienti per sommare

Question

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.

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 in a (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.

Answer 1

così ho trovato la soluzione a questo problema io stesso:

Se si dispone di valori di matrice A[i][j] e le differenze di matrice B[i][j], che avrebbe dovuto sottrarre A-B per ogni I, j. Quindi devi creare un grafico bipartito usando le righe come nodi di sinistra e le colonne come nodi di destra.

Quindi è necessario connettere ciascuno dei nodi di riga ai nodi di colonna e viceversa. Connetti anche la sorgente a tutti i nodi di riga e collega tutti i nodi della colonna al sink.

La capacità per ciascun arco dal nodo sorgente a quello riga è la somma corrente di numeri e lo stesso vale per i capati dei nodi della colonna da affondare.

Ogni capacità tra nodo di riga e nodo di colonna è la corrente B[i][j] * 2. Quindi è necessario disporre di una rete completa.

Usa Ford Fulkerson con Edmonds Karp. Il flusso tra ogni nodo di riga e nodo di colonna è il numero che deve essere aggiunto all'attuale A[i][j].

La vostra matrice A risultante sarà la vostra risposta.