Czy ktoś mógłby być tak uprzejmy i rzucić trochę światła na rozwiązanie BAL? Brut force z liczeniem maksymalnego skojarzenia w grafie dwudzielnym to oczywiście każdy umie zrobić, ale przy większych wartościach n moja pomysłowość się kończy...

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)

Z twierdzenia Kőniga wiemy, że wynik = maksymalne skojarzenie = minimalne pokrycie wierzchołkowe. Czyli chcemy wybrać jak najmniejszy zbiór cyrkowców, tak, żeby w każdym rzędzie i w każdej kolumnie zostali wybrani albo wszyscy z hula-hop, albo wszyscy bez hula-hop.

Zdefiniujmy zmienne:
a(i,j) = 1 jeśli dany cyrkowiec ma hula-hop
x(i) = 1 jeśli w rzędzie i wybieramy do pokrycia wierzchołkowego tych z hula-hop
y(j) = 1 jeśli w kolumnie j wybieramy tych z hula-hop

Cyrkowiec (i,j) zostanie wybrany chyba że x(i) = y(j) ≠ a(i,j).

Więc chcemy zminimalizować sumę:

S = suma(i,j) (1 - a(i,j)(1-x(i))(1-y(j)) - (1-a(i,j))x(i)y(j))
= n^2 - suma(i,j) a(i,j) + suma(i) x(i) suma(j) a(i,j) + suma(j) y(j) suma(i) a(i,j) - (suma(i) x(i)) * (suma(j) y(j))

Zdefiniujmy dalsze zmienne:
b = suma(i,j) a(i,j)
c(i) = suma(j) a(i,j)
d(j) = suma(i) a(i,j)

S = n^2 - b + suma x(i)c(i) + suma y(j)d(j) - (suma x(i))(suma y(j))

Jeśli posortujemy wiersze i kolumny tak, żeby c(i) i d(j) były niemalejące, to wtedy najlepiej x(i) i y(j) ustawić na 1 na jakichs początkowych ich prefiksach.

Czyli musimy wybrać jakieś liczby X i Y i przyjąć:
x(i) = 1 jeśli i <= X
y(j) = 1 jeśli j <= Y

S = n^2 - b + suma(i<=X) c(i) + suma (j<=Y)d(j) - XY

Dla danego X, najlepiej wybrać jak największe Y takie, że d(Y) <= X.
Zdefiniujmy:
e(i) = liczba j takich, że d(j)<=i.

I wtedy:
S = n^2 - b + suma(i<=X) c(i) + suma (i<=X)(Y-e(i)) - XY
= n^2 - b + suma(i<=X) (c(i) - e(i))

Więc w naszym rozwiązaniu będziemy utrzymywać liczbę b (liczba cyrkowców z hula-hop) oraz ciągi:
* nieposortowane c(i)
* nieposortowane d(j)
* posortowane c(i)
* posortowane d(j)
* e(i)
* drzewo przedziałowe liczące i minimalizujące sumy prefiksowe (c(i)-e(i))

Na początku liczymy początkowe ciągi c(i), d(j) zamiatając prostokąty od lewej do prawej oraz od góry do dołu, utrzymując drzewo przedziałowe mówiące nam dla kolejnych kolumn, którzy cyrkowcy mają hula-hop i ilu ich jest. Przy okazji dla każdej poprawki króla tutaj też obliczamy, czy ona doda czy odejmie jedno hula-hop.

Następnie sortujemy ciągi, obliczamy e(i), i inicjalizujemy sumy prefiksowe (c(i)-e(i)).

Dla każdej poprawki króla poprawiamy posortowane ciągi w odpowiednich miejscach przy pomocy wyszukiwania binarnego i wtedy wiemy też gdzie należy poprawić e(i).

Ania, Tomek - bardzo dziękuję :)
Czy nie ma jednak prostszego rozwiązania? Zadanie jest z grupy B, więc teoretycznie rozwiązanie nie powinno być tak skomplikowane?
A swoją drogą - ciekawa rzecz: bezwładność umysłowa - jakoś zafiksowałem się na tym, że z równości minimalnego pokrycia z maksymalnym skojarzeniem w grafach dwudzielnych można miło skorzystać tylko w jedną stronę - od maksymalnego skojarzenia do minimalnego pokrycia.