Temps de sequera P97149

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 x ≠ y) 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 ≤ 10⁴, n − 1 ≤ m ≤ 5 n, 1 ≤ v ≤ 10⁵, i ‍1 ≤ c ≤ 10⁵. 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.