Trilanţ

Trilant

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

Într-un graf neorientat $G=(V,E)$ cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri $S={x{~1~},x{~2~}...x{~k~}}$, cu condiţia să existe muchie între oricare două noduri consecutive, si toate nodurile să fie diferite. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni x{~1~} cu x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~} cu x{~k~}. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod, adică : $(x{~1~},x{~k~})$. Definim un trilanţ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este egal cu suma costurilor celor trei lanţuri care îl formează. Vom nota un trilanţ prin $(A,B,C)$.

Într-un graf neorientat $G=(V,E)$ cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri $S={x{~1~},x{~2~}...x{~k~}}$, cu condiţia să existe muchie între oricare două noduri consecutive, si toate nodurile să fie diferite. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni $x{~1~}$ cu $x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~}$ cu $x{~k~}$. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod, adică : $(x{~1~},x{~k~})$. Definim un trilanţ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este egal cu suma costurilor celor trei lanţuri care îl formează. Vom nota un trilanţ prin $(A,B,C)$.

h2. Cerinţa

h2. Date de ieşire

Fişierul $trilant.out$ va conţine pe prima linie costul minim găsit. Fiecare din următoarele trei linii va avea urmatorul format: $K$, urmat de $K$ numere $x{~1~},x{~2~}...x{~k~}$, reprezentand unul din cele trei lanţuri ce formeză trilanţul cerut. Cele trei lanţuri pot fi afişate îm orice ordine. În cazul în care există mai multe soluţii, se poate afişa oricare.

Fişierul $trilant.out$ va conţine pe prima linie costul minim găsit. Fiecare din următoarele trei linii va avea urmatorul format: $K$, urmat de $K$ numere $x{~1~},x{~2~}...x{~k~}$, reprezentand unul din cele trei lanţuri ce formeză trilanţul cerut. Cele trei lanţuri vor fi afisate cu nodurile in ordine de la $X$ la $A$, de la $X$ la $B$ si de la $X$ la $C$. În cazul în care există mai multe soluţii, se poate afişa oricare.

h2. Restricţii
* $1 ≤ A, B, C ≤ N ≤ 100 000$

* $1 ≤ M ≤ 500 000$
* $1 ≤ costul unei muchii ≤ 20 000$

* $1 ≤ M ≤ 250 000$
* $1 ≤ costul unei muchii ≤ 4 000 000$

* Pentru $50%$ din teste $N ≤ 1 000$
* Lanţurile care formează un trilanţ pot avea lungimi diferite
* Oricare trei lanţuri $(A,X),(B,X),(C,X)$ care formează un trilanţ vor fi disjuncte două cate două, mai puţin nodul $X$ (singurul nod comun pe care îl vor avea va fi $X$)

2 4 1
3 4 1
| 3

2 1 4
2 2 4
2 3 4

2 4 1
2 4 2
2 4 3

|
== include(page="template/taskfooter" task_id="trilant") ==

4268