Zadanie skoczki potyczki algorytmiczne - skojarzenia w grafach dwudzielnych

Question

Cześć.

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/JSkdJQdv3zPHaOLWrUCXjj8A/site/?key=statement

Oglądałem wykład o grafach dwudzielnych i skojarzeniach, prowadzący omówił jak naklepać maksymalne skojarzenie w grafie dwudzielnym, to umiem i zrobiłem, potem dał to zadanie jako "praca domowa" mówiąc, że trzeba skonstruować graf dwudzielny i napisać maksymalne skojarzenie. Problem taki, że niezbyt wiem jaki graf tu skonstruować. Jedyne co przychodzi mi do głowy jak mam plansze i chcę przekształcić do grafu dwudzielnego, to zrobić graf, że zbiór A to kolumny, B to wiersze, jak mam jakieś pole o współrzędnych (i,j), to robię krawędź i->j. Problem taki, że tutaj niezbyt widzę jak to zastosować. Jak ktoś ma jakiś pomysł jak zrobić to zadanie, to z góry bardzo dziękuję za pomoc.

Answer 1

Okazało się, że zadanie nie jest zbyt trudne. Konstrujemy graf, gdzie wierzchołek, to pole (i,j) i dajemy krawędź tam, gdzie możemy skoczyć skoczkiem z pola (i,j) oraz oba pola nie mogą być zajęte. Zauważmy, że jak skaczemy skoczkiem z pola białego, to skoczymy na pole czarne, jak skaczemy z pola czarnego, to skoczymy na pole białe, w takim razie skonstruowany graf jest dwudzielny, gdzie pola białe, to zbiór A, pola czarne to zbiór B.

Wynik to maksymalny zbiór wierzchołków zawarty z zbiorze z grafu wejściowego, w którym żadne dwa z tego zbioru nie są połączone krawędzią. Zauważmy, że liczebność tego zbioru to:

liczba wszystkich wierzchołków w grafie - max skojarzenie.

Więc puszczamy na takim grafie maksymalne skojarzenie. Trzeba być uważny, bo N <= 200, czyli możemy mieć nawet 40000 wierzchołków oraz 40000*8 krawędzi i puszczenie zwykłego algorytmu skojarzenia z break-iem, gdy znajdziemy ścieżkę powiększającą może być zbyt wolne(i jest, mi weszło na 70pkt). Jak usuniemy break-a, gdy znajdziemy ścieżkę powiększającą to wchodzi na 100 z bardzo dużym zapasem. Można dodać random shuffle na wierzchołkach i krawędziach, żeby nie było złościwego testu od orgranizatorów, który się zkwadraci, ale w tym zadaniu nawet nie było to potrzebne, co nie zmienia faktu, że moim zdaniem warto to zrobić.

Comments

Można dodać random shuffle na wierzchołkach i krawędziach, żeby nie było złościwego testu od orgranizatorów, który się zkwadraci, ale w tym zadaniu nawet nie było to potrzebne, co nie zmienia faktu, że moim zdaniem warto to zrobić.

....możesz to rozwinąć?

---

Mamy taki kod:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

const int MAXN = 205, MAXG = 40005, DELTASIZE = 8;
int n = 0, m = 0, x = 0, y = 0, wyn = 0;
bool czy_zajete[MAXN][MAXN];
vector<int> G[MAXG];
vector<int> delta_Y = {2,2,-2,-2,1,1,-1,-1};
vector<int> delta_X = {-1,1,-1,1,2,-2,2,-2};
int matched[MAXG];
bool visited[MAXG];
vector<int> V;

inline bool skoj(int v)
{
	visited[v] = true;
	for(auto x : G[v])
	{
		if(visited[x] or matched[x] != 0) continue;
		matched[v] = x, matched[x] = v, --wyn;
		return true;
	}
	for(auto x : G[v])
	{
		if(visited[x] or visited[matched[x]] or !skoj(matched[x])) continue;
		matched[v] = x, matched[x] = v;
		return true;
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	rep(i,m)
	{
		cin >> x >> y;
		czy_zajete[y][x] = true;
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			if(czy_zajete[i][j]) continue;
			rep(k,DELTASIZE)
			{
				int y = i + delta_Y[k], x = j + delta_X[k];
				if(y >= 1 and y <= n and x >= 1 and x <= n and !czy_zajete[y][x]) G[(i-1)*n+j].pb((y-1)*n+x);
			}
		}
	}

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(!czy_zajete[i][j]) ++wyn;

	for(int i = 1; i <= n*n; ++i) random_shuffle(all(G[i]));
	V.assign(n*n,-1);
	rep(i,n*n) V[i] = i+1;
	bool czy = true;
	while(czy)
	{
		czy = false;
		for(int i = 1; i <= n*n; ++i) visited[i] = false;
		rep(i,n*n) if(matched[V[i]] == 0) czy |= skoj(V[i]);
	}

	cout << wyn << '\n';

	return 0;
}

Ogólnie znajdywanie maksymalnego skojarzenia w grafie dwudzielnym pesymistycznie ma złożonność O(n*m), gdzie n to liczba wierzchołków w grafie, a m, to liczba krawędzi+liczba wierzchołków. Działa on tak, że szukamy ścieżek powiększających dopóki one istnieją (zwiększają one dotychczas rozważane maksymalne skojarzenie o 1), a jak nie istnieją to kończymy algorytm. No i jak popatrzysz sobie na tego df-sa, no to dfs jak dfs chodzimy po krawędziach i cały myk polega na tym, że jak organizatorzy dadzą swój test taki, żeby ten algorytm działał w O(n*m), to będzie działał w O(n*m), bo taką ma pesymistyczną złożonność.

Random shuffle jest po to, żeby nie było takiego złościwego testu, który powoduje O(n*m), bo takich testów jest niewiele i przy losowym ułożeniu krawędzi i wierzchołków ten algorytm działa bardzo szybko.

Ogólnie w praktyce ten algorytm z random shuffle dla krawędzi oraz wierzchołków działa bardzo szybko, praktycznie liniowo względem rozmiaru grafu. Dla N,M <= 2*10^5 raczej wchodzi nawet (tutaj weszło: https://judge.yosupo.jp/problem/bipartitematching).

Np. tutaj jest wyjaśnione szukanie maksymalnego skojarzenia w grafie dwudzielnym: https://www.youtube.com/watch?v=6tp_4dK4t3s&t=7611s