Cost màxim sense cicles P34607


Statement
 

pdf   zip

html

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 n, el nombre d’arestes m, i m triplets x y c per indicar una aresta entre x i y de cost c. Els vèrtexs es numeren de 0 a n − 1. Suposeu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5 n, i 1 ≤ c ≤ 105. Hi pot haver més d’una aresta entre dos vèrtexs, i fins i tot arestes amb x = 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++