apm

Arbore partial de cost minim

== include(page="template/taskheader" task_id="inversmodular") ==

== include(page="template/taskheader" task_id="apm") ==

Se da un graf bidirectionat $G$ cu $N$ noduri si $M$ muchii cu cost. Se cere sa se aleaga o submultime de muchii dintre aceste $M$, de cost minim, astfel incat sa existe un singur drum intre oricare doua noduri parcurgand doar muchii din submultimea aleasa.

Se da un graf conex neorientat $G$ cu $N$ noduri si $M$ muchii, fiecare muchie avand asociat un cost. Se cere sa se determine un subgraf care cuprinde toate nodurile si o parte din muchii, astfel incat subgraful determinat sa aiba structura de arbore si suma costurilor muchiilor care il formeaza sa fie minim posibila. Subgraful cu proprietatile de mai sus se va numi arbore partial de cost minim pentru graful dat.

h2. Date de intrare

Fisierul de intrare $apm.in$ va contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu.Pe urmatoarele $M$ randuri se vor gasi muchiile sub forma $X$, $Y$,$C$, cu semnificatia exista muchie intre $X$ si $Y$ cu costul $C$.

Fisierul de intrare $apm.in$ va contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu. Pe urmatoarele $M$ linii se vor gasi muchiile grafului sub forma {$X Y C$}, cu semnificatia ca exista muchie neorientata intre $X$ si $Y$ de cost $C$.

h2. Date de ieşire

Fisierul de iesire $apm.out$ va contine pe prima linie costul total minim.

Fisierul de iesire $apm.out$ va contine pe prima linie costul arborelui partial de cost minim. Pe a doua linie se va gasi numarul de muchii din arborele partial selectat. Fiecare din urmatoarele linii, pana la sfarsitul fisierului de iesire, va contine cate doua numere naturale, capetele unei muchii ce apartine arborelui solutie. Muchiile pot fi afisate in orice ordine. Daca sunt mai multe solutii corecte se poate afisa oricare.

h2. Restricţii

* $1 ≤ N ≤ 200.000$
* $1 ≤ M ≤ 200.000$
* Pentru $20%$ din teste $N,M ≤ 20$
* Pentru inca $30%$ din teste $N,M ≤ 5.000$
* Intre oricare doua noduri va exista decat o muchie.

* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 400 000$
* $-1 000 ≤ C ≤ 1 000$
* Pentru $20%$ din teste $N, M ≤ 20$
* Pentru inca $20%$ din teste $N ≤ 800$ si $M ≤ 1 500$

h2. Exemplu

h2. Exemple

table(example). |_. inversmodular.in |_. inversmodular.out |
| 9 14

table(example). |_. apm.in |_. apm.out |_. apm.in|_. apm.out|
|9 14

1 2 10
1 3 -11
2 4 11

8 9 4
9 7 3
6 7 11

| 3
|

|37
8
3 1
7 9
7 3
9 8
7 4
2 1
5 2
7 6|3 3
1 2 -3
2 3 -4
3 1 -5|-9
2
1 3
3 2|

h3. Explicaţie

h3. Explicatii

$5 * 3$ este congruent cu {$1$}, modulo {$7$}, deoarece restul impartirii lui $15$ la $7$ este {$1$}.

_Exemplul 1_: Un arbore partial de cost minim pentru graful dat poate fi format din urmatoarele muchii: ({$7, 3$}), ({$7, 4$}), ({$7, 9$}), ({$7, 6$}), ({$9, 8$}), ({$1, 3$}), ({$1, 2$}) si ({$2, 5$}). Suma costurilor acestor muchii este $37$. Solutia nu este neaparat unica.

h2. Indicaţii de rezolvare
 
Un algoritm evident ar fi incercarea tuturor numerelor $X$ intre $1$ si $N-1$ si verificarea proprietatii din enunt pentru $X$. O astfel de solutie are complexitatea {$O(N)$} si obtine 30 de puncte. Sursa se poate gasi 'aici':job_detail/223241?action=view-source.

_Exemplul 2_: Desi solutia optima ar parea la prima vedere introducerea tuturor celor 3 muchii, acest lucru nu este posibil deoarece s-ar crea un ciclu. Vor fi selectate muchiile {$(2, 3)$} si {$(3, 1)$}.

O complexitate mai buna se obtine folosind "teorema lui Euler":http://en.wikipedia.org/wiki/Euler%27s_theorem, din care avem ca <tex>A^{\varphi(N)} \equiv 1 (mod N)</tex>, unde <tex>\varphi(N)</tex> reprezinta numarul numerelor mai mici decat $N$ si prime cu $N$. Cum <tex>A^{\varphi(N)} = A * A^{\varphi(N)-1}</tex> rezulta ca <tex>A^{\varphi(N)-1}</tex> este inversul modular al lui {$A$}. Solutia problemei va fi deci <tex>A^{\varphi(N)-1} mod N</tex>. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula aceasta putere in complexitate {$O(log{~2~}N)$}. In plus, putem calcula <tex>\varphi(N)</tex> in complexitate <tex>O(\sqrt{N})</tex>. Pentru cazul particular cand $N$ este prim, <tex>\varphi(N) = N-1</tex>, deci raspunsul va fi $A^N-2^$ (dupa cum reiese si din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem). O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/227473?action=view-source.

h2. Indicaţii de rezolvare

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}N)$}. Putem folosi principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $A$ si $N$ numere intregi exista doua numere $X$ si $Y$ de asemenea intregi astfel incat {$A * X + N * Y = cmmdc(A, N)$}. Cum in problema determinarii inversului modular avem {$cmmdc(A, N) = 1$}, exista $X$ si $Y$ astfel incat {$A * X + N * Y = 1$}. Considerand ecuatia modulo $N$, deoarece {$N * Y$} este divizibil cu {$N$}, avem {$A * X$} congruent cu {$1$} (modulo $N$), deci $X$ este inversul modular pentru {$A$}. Coeficientii $X$ si $Y$ pot fi determinati in timp logaritmic. {$X$} poate sa fie si negativ, deci trebuie sa adaugam $N$ la $X$ pana cand devine pozitiv. O astfel de solutie se poate gasi 'aici':job_detail/228208?action=view-source.

O prima idee ar fi generarea tuturor submultimilor de $N-1$ muchii, verificarea daca muchiile selectate formeaza un arbore si retinerea solutiei optime. Aceasta rezolvare este cea mai evidenta dar are complexitate exponentiala si obtine aproximativ $20$ de puncte.
Presupunand ca sunt deja alese $N-2$ muchii care nu formeaza cicluri, in alte cuvinte formeaza $2$ arbori, trebuie sa se mai aleaga inca o muchie, si anume muchia minima care garanteaza conectivitatea arborilor. De la aceasta idee deducem ca cel mai bine ar fi sa adaugam muchii de cost minim, cat timp aceste muchii nu creaza cicluri.
Daca se sorteaza muchiile crescator dupa costul asociat si se parcurg in ordinea sortarii, este mereu util sa adaugam la solutie muchia de cost minim cat timp aceasta nu creaza un ciclu, sau altfel spus, nodurile pe care le uneste nu sunt deja in aceeasi componenta conexa. Aceasta solutie are complexitate $O(N*M + Mlog{~2~}M)$, deoarece iterarea prin cele $M$ muchii are complexitate {$O(M)$}, iar 'parcurgerea dfs':problema/dfs pentru verificarea ciclurilor se realizeaza in timp {$O(N)$} la fiecare pas. O astfel de solutie obtine 40-50 de puncte, in functie de implementare, si se poate vedea 'aici':job_detail/234746?action=view-source.
Pentru a optimiza solutia de mai sus este suficient la fiecare pas sa verificam daca cele doua noduri pe care le uneste muchia curenta sunt in aceeasi componenta conexa, operatie care se poate realiza in timp {$O(log*N)$}, cu ajutorul 'multimilor disjuncte':problema/disjoint. Astfel complexitatea se reduce la $O(Mlog*N + Mlog{~2~}M)$. Acest algoritm este prezentat si "aici":http://en.wikipedia.org/wiki/Kruskal%27s_algorithm si se numeste algoritmul lui Kruskal. O implementare pe aceasta idee se gaseste 'aici':job_detail/234736?action=view-source.
Pentru a intelege o alta solutie se presupune urmatorul scenariu: existand deja calculat un subarbore minim vrem sa introducem in el inca un nod. Evident vom introduce nodul care are muchia de cost minim care il leaga de subarborele deja format. Aceasta solutie are complexitate $O(N*M)$, deoarece incepem cu un nod aleator si adaugam rand pe rand toate nodurile ramase. Acest algoritm se poate optimiza, daca pentru fiecare nod se tine muchia minima curenta care il leaga de subarborele existent. La fiecare introducere a unui nod in subarbore, se actualizeaza toti vecinii lui. Aceasta solutie are complexitate $O(N^2^)$ si ar trebui sa obtina $50$ puncte. Trebuie in plus precizat ca in cazul in care graful este dens (numarul de muchii $M$ este de ordinul {$O(N^2^)$}) aceasta abordare este de preferat celor cu alte complexitati.
Pentru a se optimiza mai departe algoritmul pentru extragerea minimului se foloseste un {"heap":http://en.wikipedia.org/wiki/Heap_(data_structure)}, iar de fiecare data cand se introduce un nod in subarbore sunt parcurse muchiile incidente cu el si se actualizeaza nodurile vecine. Astfel complexitatea devine $O(M*log{~2~}N)$. Algoritmul este cunoscut in literatura de specialitate ca "Algoritmul lui Prim":http://en.wikipedia.org/wiki/Prim%27s_algorithm. O sursa pe acesta idee se poate vedea 'aici':job_detail/234741?action=view-source.

h2. Aplicatii

O aplicatie foarte utila a inversilor modulari este calcularea combinarilor, modulo un numar prim $P$ dat. De exemplu, avem:
 
<tex>C^K_N = \frac{N!}{K!*(N-K)!} = N! * (K!)^{-1} * [(N-K)!]^{-1}</tex>
 
Prin <tex>(K!)^{-1}</tex> si <tex>[(N-K)!]^{-1}</tex> se inteleg inversii modulari ai acestor numere, modulo {$P$}. Astfel putem calcula o combinare de ordin $N$, modulo $P$, in timp {$O(N)$}.
 
Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:

* 'Desen':problema/desen
* 'Radiatie':problema/radiatie
* "Aviamachinations":https://codeforces.com/problemsets/acmsguru/problem/99999/323

* "Stand in Line":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115
* 'Functii':problema/functii
== include(page="template/taskfooter" task_id="inversmodular") ==

== include(page="template/taskfooter" task_id="apm") ==

public

task: apm

3509