Maxflow? P32404


Statement
 

pdf   zip

thehtml

Hi ha problemes, com el maxflow, que són tan clàsics que no calen gaire explicacions: Donat un graf no dirigit amb capacitats a les arestes, podeu calcular el flux màxim entre el vèrtex 0 i el vèrtex 1?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n, el nombre d’arestes m, i m triplets x y c indicant una aresta entre x i y (amb xy) de capacitat c. Podeu suposar 2 ≤ n ≤ 104, 0 ≤ m ≤ 2, que els vèrtexs es numeren des de 0, que hi pot haver més d’una aresta entre el mateix parell de vèrtexs, i 1 ≤ c ≤ 105.

Sortida

Per a cada graf, escriviu el flux màxim entre el vèrtex 0 i el vèrtex 1.

Public test cases
  • Input

    3 1
    1 0 10
    
    2 0
    
    4 2
    0 3 200
    1 3 300
    

    Output

    10
    0
    200
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++