Zadanie
Hurááá! Prázdniny! Povedal si Samko a začal sa tešiť na ničím nerušený oddych. Konečne bude môcť robiť všetko, na čo počas roka nebol čas. Dievčatá, plávanie, opaľovanie sa, dievčatá, ochutnávka kávy, dievčatá, hranie spoločenskej hry, dievčatá, sledovanie obláčikov, učenie sa, spoločenská hra, ochutnávka nemeckých klobás, dievčatá, spánok, spoločenská hra, túra a tak ďalej. Keď má človek ale toľko plánov, musí si ich poriadne naplánovať.
Začal teda rozmýšľať, čo ktorý deň urobí. Nie všetko sa totiž hodí na ľubovoľný deň. Napríklad takého 5.9. určite nie je čas na dievčatá, ale deň po tom je už fajn. Takisto Samko vie, že v jeden deň spraví maximálne jednu vec. Ak by totiž riešil dievčatá, tak na taký spánok mu naozaj čas nezostane.
Prišiel teda s perfektným nápadom. Na každý deň si stanovil štyri (nie nutne rôzne) alternatívy. Potom sa znovu zamyslel a poriadne si spísal, aké veci chce cez prázdniny naozaj stihnúť. Na poradí mu nezáleží, ale ak si raz naplánoval opaľovanie a opaľovanie, tak sa chce naozaj opaľovať dva krát. Je však naozaj možné, aby stihol všetky naplánované aktivity?
Úloha
Prázdniny majú \(n\) dní. Na každý deň má Samko vybrané štyri možné aktivity, z ktorých môže maximálne jednu ten deň vykonávať. Na celé prázdniny má zoznam \(k\) aktivít, ktoré chce stihnúť. Je to ale možné? Koľko najviac toho dokáže absolvovať?
Formát vstupu
V prvom riadku vstupu je číslo \(n\) (\(1\leq n \leq 10\,000\)) udávajúce počet prázdninových dní. Nasleduje \(n\) riadkov so štyrmi číslami \(a_1 , a_2, a_3, a_4 \leq 1\,000\,000\) oddelenými medzerou, predstavujúce možné aktivity na daný deň. V nasledujúcom riadku je číslo \(k\) (\(1 \leq k \leq 10\,000\)) udávajúce počet aktivít, ktoré chce Samko cez prázdniny stihnúť. V nasledujúcom riadku sa nachádza \(k\) kladných čísiel menších ako \(1\,000\,000\), popisujúce jednotlivé aktivity.
Formát výstupu
Vypíšte jedno číslo – najväčší počet aktivít, ktoré môže Samko cez prázdniny naozaj stihnúť.
Príklad
Input:
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
Output:
5
S výnimkou predposledného dňa sa bude zúčastňovať aktivity číslo \(2\). V predposledný deň sa zúčastní aktivity \(10\).
Input:
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
Output:
4
Tu sa Samko musí rozhodnúť, či si dá tretí deň aktivitu 3 alebo 4. Jednu z nich určite neabsolvuje.
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.1
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 cesta2.
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})\)3.
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.4
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)\)5.
#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());
}
Bipartitný graf je taký, u ktorého vieme vrcholy rozdeliť do dvoch množín, tzv. partícií, tak, aby žiadne hrany neviedli v rámci jednej partície.↩
Ak by ste si to chceli formálne dokázať, najjednoduchší postup pre netriviálnu implikáciu je nepriamy dôkaz. Vezmete si nejaké nie maximálne párenie a nejaké maximálne, pozriete sa, ako by vyzerali komponenty grafu, ktorý bude obsahovať všetky vrcholy, ale len hrany, koré sú aspoň v jednom z párení, a zistíte, že musí existovať zlepšujúca cesta.↩
Stačí sa pozrieť, po ktorých hranách medzi dňami a aktivitami tečie voda.↩
Tu sa hodí ešte poznamenať, že pre všeobecné grafy existujú aj lepšie tokové algoritmy, ale vďaka malému hornému odhadu veľkosti toku nám v tomto prípade stačí aj takéto "pomalé" riešenie.↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.