8. Organizačné opletačky vzorové riešenie

5
1 2 2 1
2 2 3 4
3 2 6 7
10 3 2 1
10 2 1 5
5
2 10 2 2 2

5

5
1 5 2 8
1 2 5 9
1 3 4 6
1 5 1 2
2 1 7 8
5
1 2 3 4 5

4

Najprv sa pozrime na to, čo po nás vlastne zadanie chce. Potrebujeme nejako vhodne povyberať z každého dňa konkrétnu aktivitu tak, aby sme čo najlepšie pokryli všetky aktivity, ktoré chce Samko stihnúť. Pre nás je ale vhodnejší iný pohľad: hľadajme také pospájanie aktivít s dňami (v ktorých sa daná aktivita vyskytuje), kde každý deň je spojený s najviac jednou aktivitou zo Samkovho zoznamu a podobne aj každá aktivita je spojená s najviac jedným dňom. Skúsenejší riešitelia hneď zbadajú párenie, dokonca (a našťastie) na bipartitnom grafe.¹

Zostavíme si teda graf, v ktorom ako vrcholy jednej partície pôsobia aktivity, ktoré chce Samko stihnúť, a ako vrcholy druhej partície pôsobia jednotlivé dni, ktoré má k dispozícii. Hrana medzi dňom a aktivitou existuje práve vtedy, keď ju môže Samko v ten deň vykonávať. Nás bude zaujímať, koľko najviac hrán z tohto grafu vieme vybrať tak, aby žiadne dve nemali spoločný koncový vrchol. Takúto množinu hrán nazveme maximálnym párením. Počet hrán maximálneho párenia bude našou hľadanou odpoveďou.

Maximálne párenie

Pre popis algoritmu hľadajúceho maximálne párenie si zavedieme ešte jeden pojem: zlepšujúca cesta v nejakom už vybratom (nie maximálnom) párení \(P\). Ide o postupnosť neopakujúcich sa vrcholov (spojených hranami), ktorá začína v nespárenom vrchole \(v_0\), pokračuje po nepoužitej hrane do nejakého vrchola \(u_0\). Kým táto cesta neskončí v nespárovanom vrchole, pokračuje ďalej z vrchola \(u_i\) do vrchola \(v_{i+1}\), po hrane z párenia \(P\), z ktorého pokračuje do vrchola \(u_{i+1}\) opäť po hrane, ktorá sa v párení \(P\) nenachádza. Všimnime si, že cesta ide z vrcholov \(v\) po nespárenej hrane a z vrcholov \(u\) po spárenej. Keďže cesta začína vo vrchole \(v_0\) a končí v nejakom vrchole \(u_k\), bude obsahovať viac nespárených, než spárených hrán.

Keď nájdeme zlepšujúcu cestu v nejakom párení, vieme toto párenie zväčšiť o 1, pokiaľ "preklopíme" hrany na tejto zlepšujúcej ceste, čiže tie hrany z cesty, ktoré sme mali pôvodne v párení, z neho odstránime a zvyšné doňho pridáme. Existuje dôkaz, že párenie je maximálne práve vtedy, keď v ňom neexistuje zlepšujúca cesta².

Preto sa bude celé riešenie párenia zaoberať hľadaním zlepšujúcich ciest na bipartitnom grafe. Označme si partície tohto grafu ako \(A\) a \(B\). Stačí nám používať obyčajné prehľadávanie do hĺbky, ktoré vždy začne napríklad v (každom) nespárenom vrchole z \(A\), pôjde do každého možného vrchola z \(B\) po nespárenej hrane, potom po spárenej hrane späť do vrchola z \(A\), atď. atď., až dôjde do nespáreného vrchola z \(B\). V tomto momente "preklopí" všetky hrany.

Toto celé sa bude opakovať, kým sa nestane, že nenájdeme žiadnu zlepšujúcu cestu. Vtedy však môžeme byť spokojní, lebo sme objavili maximálne párenie.

Časová zložitosť takéhoto riešenia je \(O(m \cdot (v + h))\), kde \(m\) je veľkosť maximálneho párenia, \(v\) je počet vrcholov nášho grafu a \(h\) je počet hrán tohto grafu. \(m\) vieme zhora odhadnúť ako \(min(n, k)\), \(v = n + k\). V najzákernejšom prípade však môže byť počet hrán až \(n \cdot k\), napríklad ak máme \(k\)-krát tú istú aktivitu, ktorá sa môže vykonať v každý deň.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

int n,k;
int A[100047][4];
vector<vector<int> > G;
vector<bool> T;
vector<int> P;

bool zlepsi(int v) {
    T[v]=true;
    For(i,G[v].size()) {
        int w=G[v][i];
        if(P[w]==-1) {P[w]=v; return true;}
        if(!T[P[w]] && zlepsi(P[w])) {P[w]=v; return true;}
    }
    return false;
}

int matching() {
    P.resize(n+k,-1);
    int res=0;
    For(i,n) {
        T.clear(); T.resize(n,false);
        if(zlepsi(i)) res++;
    }
    return res;
}

int main() {
    scanf("%d",&n);
    For(i,n) For(j,4) scanf(" %d",&A[i][j]);
    scanf(" %d",&k);
    G.resize(n+k);
    For(i,k) {
        int x;
        scanf(" %d",&x);
        For(j,n) For(k,4) if(A[j][k]==x) G[j].push_back(n+i);
    }
    printf("%d\n",matching());
return 0;
}

Kam ďalej

Prvé možné zlepšenie je v samotnom algoritme hľadajúcom maximálne párenie. Keby sme namiesto prehľadávania do hĺbky použili prehľadávanie do šírky, vieme nájsť viacero zlepšujúcich ciest naraz a vieme to ukopať k časovej zložitosti \(O(h \cdot \sqrt{v})\)³.

S tým sa však neuspokojíme a potiahneme to kúsok ďalej. Čo nám vedelo strašne pokaziť časovú zložitosť, boli viacnásobné aktivity. S nimi sa vieme vysporiadať tak, že všetky rovnaké aktivity pospájame do jedného vrchola, v ktorom si nejako označíme, že s ním môže byť pospájaných viacero rôznych dní. Namiesto toho, aby sme nejako čarovne upravovali pôvodný algoritmus pre párenie, si ukážeme, ako sa celá úloha dá previesť na úlohu o maximálnom toku v grafe.

Na to si zostrojíme ešte trošku iný graf. Ten bude ohodnotený a orientovaný a bude obsahovať dva špeciálne vrcholy, takzvaný source a sink, ďalej vrcholy pre každý deň a pre každý druh aktivity. Zo source pôjde hrana do každého dňa s váhou \(1\). Z každého dňa pôjdu hrany váhy \(1\) do tých aktivít, ktoré sa dajú v ten deň vykonávať. Tu si treba uvedomiť, že každý druh aktivity bude mať priradený nanajvýš jeden vrchol, takže týchto hrán už bude nanajvýš \(4n\). Nakoniec pôjdu hrany z jednotlivých aktivít do sink, s váhou rovnou tomu, koľkokrát chce Samko danú aktivitu počas prázdnin vykonať. Ak chceme znížiť nejaké konštanty, vrcholy budeme vytvárať len pre tie aktivity, ktoré chce Samko vykonať počas prázdnin.

Maximálne toky

V takomto novom grafe nás bude zaujímať, koľko najviac vody vie tiecť zo source do sink. Obmedzenia sú nasledovné: Z každého vrchola okrem source a sink musí odtekať presne toľko vody, koľko doňho priteká a po každej hrane môže tiecť najviac toľko vody, aká je jej váha. Ľahko si všimneme, že každý validný tok zodpovedá nejakému konkrétnemu páreniu na pôvodnom grafe.⁴

Ako sa taký najväčší tok hľadá? Opäť budeme potrebovať zaviesť rafinovaný pojem zlepšujúcej cesty. K tomu budeme potrebovať do nášho orientovaného grafu prirobiť fiktívnu spätnú hranu ku každej normálnej hrane, na začiatku s kapacitou \(0\). V pôvodných hranách si budeme pamätať, koľko vody nimi môže ešte pretiecť, v spätných, koľko vody tečie pôvodnými hranami. Teraz budeme hľadať také cesty, ktoré začínajú v source, prechádzajú po hranách s nenulovými hodnotami a končia v sink.

Čomu to zodpovedá: Budeme hľadať nejaký spôsob, ako cez náš graf pretlačiť ďalší prúd veľkosti \(1\). Keď pôjdeme po obyčajných hranách, bude to zodpovedať tomu, že cez ne posielame nový prúd. Keď pôjdeme po spätnej hrane z \(u\) do \(v\), znamená to, že sme si rozmysleli, kade tiekol prúd predtým z \(v\) a pošleme ho nejakým novým smerom.

Tieto zlepšujúce cesty môžme opäť hľadať starým osvedčeným prehľadávaním do hĺbky zo source. Akonáhle dôjdeme do sink, hodnoty všetkých hrán, po ktorých sme prešli, znížime o \(1\) a k nim opačným hranám naopak zvýšime hodnoty o \(1\). Rozmyslite si, že opäť platí príjemná vlastnosť, že ak nevieme nájsť zlepšujúcu cestu, znamená to, že náš tok je už naozaj najväčší možný.

Časová zložitosť takéhoto riešenia bude \(O(p \cdot (v + h))\), kde \(p\) je veľkosť toku, čiže naša odpoveď, \(v\) a \(h\) sú počty vrcholov a hrán, pričom tentoraz vieme odhadnúť \(v = n + k + 2\), \(h \leq 5n + k\), takže po vhodnom dosádzaní a prepisovaní je horný odhad \(O((n + k)^2)\). Pamäťová zložitosť takéhoto riešenia bude \(O(n + k)\)⁵.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

#define For(i, n) for(int i = 0; i<int(n); ++i)
#define ForEach(it, T) for(auto it = T.begin(); it!=T.end(); ++it)
typedef vector<int> vi;
typedef vector<vi> vvi;

int n, d, k, a;
vi V; // Visited
vvi D,O,S,P; // Dni, Ostava_kapacita, Sused, oPacny_tok
map<int, int> M;

inline void makeEdge(int f, int t, int c){ //from, to, kapacita
    P[f].push_back(O[t].size());
    P[t].push_back(O[f].size());
    S[f].push_back(t);
    S[t].push_back(f);
    O[f].push_back(c);
    O[t].push_back(0);
}

bool najdi(int v){ //dfs na vrchole v
    if (V[v]) return 0;
    V[v] = 1;
    if (v==1) return 1;
    For(i, S[v].size())
        if(O[v][i] > 0 && najdi(S[v][i])) {
            O[v][i]--;
            O[S[v][i]][P[v][i]]++;
            return 1;
        }
    return 0;
}

int flow(){ //hlada najvacsi tok
    int f = 0;
    while(true) {
        V.clear();
        V.resize(n,0);
        if(!najdi(0)) break;
        f++;
    }
    return f;
}

int main(){
    scanf("%d", &d);
    D.resize(d, vi(4));
    For(i, d) For(j, 4) scanf("%d", &D[i][j]);
    scanf("%d", &k);

    //na zapamatanie mnozstva aktivit pouzijeme mapu <cislo_akivity,doterajsi_pocet>
    For(i, k) {
        scanf("%d", &a);
        M[a]++;
    }

    //pocet vrcholov bude 2(source+sink) + pocet dni + pocet roznych aktivit
    n = 2+d+M.size();
    P.resize(n);
    S.resize(n);
    O.resize(n);

    //pridame hrany z aktivit do sinku, hodnotu mame ulozenu v mape
    //vrcholy tvorime len pre aktivity, ktore chce Samko spravit
    int p = 0;
    ForEach(it, M) {
        makeEdge(2+d+p, 1, it->second);

        //ked vyuzijeme to, kolko bolo aktivit, v mape prepiseme hodnotu
        //na cislo vrchola, aby sme ho neskor (*) vedeli zistit
        it->second = 2+d+p;
        p++;
    }

    //pridavame hrany k dnom
    For(i, d) {
        //zo source do dna, kapacity 1
        makeEdge(0, 2+i, 1);
        
        //z dna do kazdej aktivity (ktoru chce Samko vobec vykonat),
        //ktora sa da v dany den vykonat
        //Z (*) vieme, ze cislo vrchola pre danu aktivitu mame teraz v mape
        //Vsimnite si, ze nasobne hrany nam nic nepokazia,
        //lebo tok do dna nikdy nepresiahne 1.
        For(j, 4) if (M.count(D[i][j])) makeEdge(2+i, M[D[i][j]], 1); 
    }
    printf("%d\n", flow());
}