P3544 [POI 2012] BEZ-Minimalist Security

题目描述

**译自 POI 2012 Stage 3. Day 2「[Bezpieczeństwo minimalistyczne](https://szkopul.edu.pl/problemset/problem/aSbIC_LB4H-CGMYPEVue5jFw/site/?key=statement)」** 给定一张无向图,点有点权 $p(v)$,边有边权 $b(u,v)$,初始时保证对每条边有 $p(u) + p(v) \ge b(u,v)$。 现在需要减少一部分点的点权,使得对每条边都恰有 $p(u) + p(v) = b(u,v)$. 求整张图减少的点权和的最小值和最大值。

输入格式

输出格式

说明/提示

对于 $56\%$ 的数据有 $n \le 2000,m \le 8000$. 对于所有数据有 $1 \le n \le 500\ 000,0 \le m \le 3\ 000\ 000$. 翻译来自于 [LibreOJ](https://loj.ac/p/2702)。