Peso massimo corrispondenza bipartita

Question

Ho un grafico in forma di una griglia rettangolare, cioè i nodi N e 2N bordi, tutti i nodi adiacenti sono collegati. Ciò significa che è due colorabile, e quindi è possibile fare corrispondenza bilaterale su di esso.

Ogni (non orientato) bordo ha un peso assegnato - o -2, -1, 0, 1 o 2. altri valori permessi

Come potrei fare per trovare l'abbinamento in questo grafico che massimizza la somma dei pesi della corrispondenza? Pseudocodice sarebbe bello, non perdere tempo con linguaggi specifici.

Idealmente, sto cercando un algoritmo che viene eseguito in tempo quadratica -. Forse O (n ^ 2 log n) nel peggiore dei casi

---

Prima di proporre una soluzione, ho provato a fare una partita di max usando bordi del peso 2, quindi di peso 1 (senza andare oltre bordi del peso 2). Ho segnato il 98% con questa implementazione (il problema è da un informatico Olimpiadi), e si chiede qual è la soluzione al 100%.

Answer 1

Non certo perché si sta pensando di min taglio. Un taglio non è garantito per darvi corrispondenza in questo caso. Quello che dovete fare è risolvere il problema di assegnazione. Assegnazione problema . I successivi brevi risolve algoritmo matematico in O (log EV V), che nel tuo caso è O (n ^ 2 log n).