Fişierul intrare/ieşire:symmetricgraph2.in, symmetricgraph2.outSursăAlgoritmiada 2016 - Runda 4 - Seniors
AutorMihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Symmetricgraph2

Aţi încercat vreodată să construiţi teste pentru probleme de flux? E neplăcut. Prietenul vostru, pe care, pentru a-i păstra anonimitatea, îl vom numi Xdărăscu, v-a sugerat următoarea construcţie: Se ia un arbore neorientat cu rădăcină, T1, o copie identică a sa, T2, iar fiecare frunză din T1 se leagă cu frunza sa corespunzătoare din T2 printr-o muchie, de-asemenea neorientată. Se pun capacităţi pe muchii după gust. Rădăcina lui T1 va fi sursa reţelei de flux, iar rădăcina lui T2 va fi destinaţia reţelei.

Totuşi, ăsta nu ar fi un test foarte bun. Ca să-i demonstraţi asta lui Xdărăscu, v-aţi hotărât să scrieţi un algoritm care calculează fluxul maxim într-o astfel de reţea pentru instanţe mult mai mari ale problemei decât ar fi posibil în mod normal.

Date de intrare

Fişierul de intrare symmetricgraph2.in va conţine pe prima sa linie valorile N şi M reprezentând numărul de noduri, respectiv de muchii ale grafului. Următoarele M linii conţin câte un triplet de numere X Y C cu semnificaţia că există o muchie neorientată de capacitate C între nodurile X şi Y.

Date de ieşire

În fişierul de ieşire symmetricgraph2.out se va afla o singură valoare, reprezentând cantitatea maximă de flux ce poate fi trimisă prin reţeaua descrisă în fişierul de intrare.

Restricţii şi precizări

  • 4 ≤ N ≤ 100.000
  • Capacitatea unei muchii este un număr natural în intervalul [1, 109].
  • Pentru 40% din punctaj, N ≤ 2.000
  • Sursa reţelei descrise în input este nodul 1, iar destinaţia este nodul N. Se garantează că graful a fost construit după metoda descrisă în enunţ.
  • Rădăcina nu este luată în calcul ca frunză, deşi poate avea gradul egal cu 1.

Exemplu

symmetricgraph2.insymmetricgraph2.out
10 11
1 2 10
1 9 4
9 8 2
8 10 3
2 3 8
2 5 4
3 4 7
4 7 9
7 10 7
5 6 1
6 7 3
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?