Data una matrice A con 0 e 1 voci. I vicini di a [i, j] sono un [i-1, j], un [i + 1, j], un [i, j-1] e un [i, j + 1] (se ne esiste uno).
Le altre voci di contatto sono una coppia impropria se non hanno valori uguali. se il numero di coppie impropri di matrice A è uguale a q, allora la penalità di matrice sarà uguale a b * q (che b è un numero naturale).
Prima di calcolare la penalità, possiamo inverse alcune voci (0 - > 1 o 1 - > 0) con costo di a (per ogni inversione di entrata). L'obiettivo è ridurre al minimo la somma del costo di inversione e della penalità finale ; Un algoritmo (con l'aiuto del flusso di rete) dovrebbe essere proposto per questo obiettivo.
La mia idea per iniziare: Presumo che ogni voce sia un nodo, quindi creo un nodo s e lo colleghi a tutte le voci 0. Quindi crea un nodo t e collega tutte le 1 voci ad esso.