Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | meta.in, meta.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
|
| Timp de execuție pe test | 0.2 sec | Limită de memorie | 8192 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Meta (clasele 11-12)
Elevii din Vianu înțeleg atât de bine algoritmii pentru găsirea arborelui parțial de cost minim, încât îi pot implementa și cu ochii închiși. De aceea, profesorul le-a dat o problemă ceva mai grea: găsirea celui de-al doilea arbore parțial în ordinea costului.
Se dă un graf neorientat cu N noduri și M muchii. Fiecare muchie are un cost pozitiv asociat și toate muchiile au costuri diferite.
Ajutați-i pe elevii din Vianu să calculeze costul celui de-al doilea arbore parțial minim. Mai exact, se cere cel mai mic număr natural K cu proprietățile:
- Există un arbore parțial de cost total K.
- K este strict mai mare decât costul arborelui parțial de cost minim pentru graful dat.
Date de intrare
Fișierul de intrare meta.in conține pe prima linie numerele N și M, despărțite printr-un spațiu. Pe următoarele M linii se găsește câte o pereche de numere x y cu semnificația că între nodurile x și y există o muchie.
Date de ieșire
În fișierul de ieșire meta.out se va tipări doar numărul K.
Restricții
- 1 ≤ N ≤ 1.000
- 1 ≤ M ≤ 300.000
- Nodurile sunt numerotate de la 1 la N.
- Costurile muchiilor sunt numere naturale distincte cuprinse între 1 și 1.000.000$.
Exemplu
| meta.in | meta.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
