algorithm - teorema - Algoritmos: uso del flujo máximo para calcular los valores correctos de la matriz

ruta mas corta

Question

Me dan una matriz A con tamaño N x M con N,M <= 100 . La matriz A consta de valores enteros A (i, j) donde i y j son 0 < i < M y 0 < j < N . También me dan las sumas de las columnas "correctas" y las sumas de fila de la matriz. Los valores dados A (i, j) son "incorrectos" (no coinciden con las sumas "correctas") y, por lo tanto, se nos proporcionan los correspondientes valores de "incorrección" B (i, j), donde B (i, j) oscila de 0 a A (i, j).

El objetivo es calcular los valores "correctos" C (i, j) en la matriz, donde A(i,j) - C(i,j) =< B(i,j) , el C (i, j) los valores también deben coincidir con las sumas de fila y columna dadas. Creo que tengo que usar el flujo máximo, pero mis intentos no han funcionado. ¿Cómo puedo conseguir esto?

Answer 1

Te daré un ejemplo aquí.

matrix A:
 10 10 10
 10 10 10
 10 10 10

matrix B:
  2  3  4
  5  6  4
  3  2  1

matrix A-B:
  8  7  6
  5  4  6
  7  8  9

Entonces tienes la fórmula A [i, j] - C [i, j] <= B [i, j]. Puedes transformarlo en A [i, j] - B [i, j] <= C [i, j] lo que significa que B [i, j] es lo más pequeño que necesitas restar de A [i, j ] para obtener algo más pequeño o igual a C [i, j]. Desde aquí sabes que necesitas agregar algo a las entradas en la matriz AB.

Veamos ahora qué y dónde agregar.

Supongamos que tiene los siguientes tamaños de filas y columnas:

c1 = 20/20
c2 = 19/21
c3 = 21/24

r1 = 21/21
r2 = 15/17
r3 = 24/27

Arriba escribí cosas en forma de:

(current flow through column or row) / (goal flow through column or row).

Ahora construyamos una red:

Ahora tenga en cuenta que la suma total de filas = suma total de columnas. Entonces intenta presionar ''suma dada de entradas'' - ''suma actual de entradas'' de ''s'' a ''t''.

Ahora, supongamos que los nodos se enumeran de izquierda a derecha por números naturales. Ahora, cuando empuja algo desde un nodo de segundo nivel a un nodo de tercer nivel, por ejemplo, empuja algo desde el nodo i, al nodo j, también agrega lo que empujó a NewMatrix [i, j], donde NewMatrix es la matriz AB y obtienes la matriz que quieres.

También tenga en cuenta que al principio, en la matriz AB, tenía la C [i, j] más pequeña que tenía que restar de A [i, j] para obtener algo más pequeño o igual a B [i, j], y ahora que agregaste algo a esa C [i, j] la desigualdad A [i, j] -C [i, j] <= B [i, j] aún se cumple.