Xarxa de carreteres P64299


Statement
 

pdf   zip

thehtml

Un país té n ciutats i m carreteres bidireccionals, les quals permeten anar de qualsevol ciutat a qualsevol altra, ja sigui de forma directa o passant per ciutats intermèdies. Cada carretera té un cert cost de manteniment. A més, el govern considera que algunes de les carreteres són imprescindibles.

Per reduir costos, el govern vol escollir el subconjunt més barat de carreteres que inclogui totes les carreteres imprescindibles i amb el qual es pugui seguir anant de qualsevol ciutat a qualsevol altra ciutat. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides d’m quàdruples x y c i, una per carretera, on x i y són les ciutats connectades directament (amb xy), c és el cost de manteniment de la carretera, i i és un càracter que és ‘I’ o ‘N’ depenent de si la carretera és imprescindible o no.

Suposeu 2 ≤ n ≤ 104, n − 1 ≤ m ≤ 5n, que la xarxa de carreteres és connexa, que les ciutats es numeren entre 0 i n−1, que no hi ha més d’una carretera entre dues ciutats x i y, i que cada c està entre 0 i 104.

Sortida

Per a cada cas, escriviu el mínim cost d’una xarxa de carreteres que compleixi les restriccions demanades.

Public test cases
  • Input

    3 2
    0 1 10 I
    0 2 20 N
    
    3 3
    0 1 10 I
    0 2 20 N
    2 1 30 I
    
    3 3
    0 1 10 I
    0 2 20 I
    2 1 30 I
    
    3 3
    0 1 10 N
    0 2 20 N
    2 1 30 N
    

    Output

    30
    40
    60
    30
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++