Cost màxim sense cicles P34607


Statement
 

pdf   zip

Donat un graf no dirigit amb costs positius a les arestes, escolliu-ne un subconjunt d’arestes de manera que no hi hagi cicles i que la suma de costs sigui màxima.

Entrada

L’entrada consisteix en diversos grafs, cadascun definit amb el nombre de vèrtexs nn, el nombre d’arestes mm, i mm triplets xx yy cc per indicar una aresta entre xx i yy de cost cc. Els vèrtexs es numeren de 0 a n−1n - 1. Suposeu 1≤n≤1041 \le n \le 10^4, 0≤m≤5n0 \le m \le 5 n, i 1≤c≤1051 \le c \le 10^5. Hi pot haver més d’una aresta entre dos vèrtexs, i fins i tot arestes amb x=yx = y.

Sortida

Per a cada graf, escriviu el cost màxim possible.

Public test cases

  • Input

    3 2  0 2 10  2 1 30
3 3  0 2 10  2 1 30  1 0 20
1 0
5 9  1 0 40  0 3 60  1 2 20  2 1 10  1 4 30  4 4 80  2 1 70  3 1 30  4 2 20
5 4  1 2 23  3 0 42  4 0 10  3 4 20

    Output

    40
50
0
200
85
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++