Temps de sequera P97149


Statement
 

pdf   zip

thehtml

La comunitat de regants d’una comarca ha decidit prendre mesures davant de la sequera actual. Per evitar la pèrdua d’aigua per evaporació, es vol reduir el nombre de canals pels quals es farà circular l’aigua. Més concretament, dels canals existents, s’ha de decidir per quins circularà aigua i per quins no, sempre garantint que tots els camps quedin irrigats (és a dir, que la xarxa de canals sigui connexa). A més, en la mesura del possible també es volen rebaixar les despeses de manteniment dels canals.

Per tot això es disposa d’un graf etiquetat, no dirigit i connex, on els vèrtexs són camps, les arestes canals, i el pes de cada aresta és un parell de nombres: el volum d’aigua que s’evapora cada dia al canal, i el cost diari de mantenir el canal en funcionament. L’objectiu és, en primer lloc, minimitzar la quantitat total d’aigua que s’evapora cada dia; i en cas d’emptat, minimitzar la despesa total diària de manteniment.

Entrada

L’entrada consisteix en diversos grafs, cadascun definit amb el nombre de vèrtexs n, el nombre d’arestes m, i m quaternes x y v c per indicar una aresta entre x i y (amb xy) en la qual s’evaporen v unitats d’aigua cada dia, i amb un cost de manteniment diari de c ‍unitats. Els vèrtexs es numeren de 0 a n − 1. Suposeu 2 ≤ n ≤ 104, n − 1 ≤ m ≤ 5 n, 1 ≤ v ≤ 105, i ‍1 ≤ c ≤ 105. Hi pot haver més d’una aresta entre dos vèrtexs.

Sortida

Per a cada cas, escriviu la mínima evaporació total possible, i també la mínima despesa total de manteniment. Prioritzeu minimitzar l’evaporació total.

Public test cases
  • Input

    3 3  1 0 2 30  2 0 2 20  1 2 9 10
    3 3  1 0 2 30  2 0 2 20  1 2 2 10
    5 6  0 1 3 10  0 2 8 20  1 3 5 30  2 3 2 40  2 4 4 50  3 4 4 45
    5 6  0 1 3 10  0 2 8 20  1 3 5 30  2 3 2 40  2 4 4 50  3 4 4 55
    

    Output

    4 50
    4 30
    14 125
    14 130
    
  • Information
    Author
    Enric Rodriguez
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python