#PQJ152x4167. QOJ 152_4167
QOJ 152_4167
城市规划 area.pas/cpp/c 时间限制 5S 空间限制 256MB
【题目描述】 小猪iPig 来到了一个叫做pigsty 的城市里,pigsty 是一座专门为小猪所准备的城市,城 市里面一共有n 个小区给小猪们居住,并且存在许多条无向边连接着许多小区。因为这里是 一个和谐的城市,所以小猪iPig 准备在这个城市里面度过他的余生。 若干年之后小猪iPig 当上了规划局长,这件事令他非常开心。不过与此同时pigsty 城 市里面出现了许多反和谐主义者,他们已经厌烦了这样和谐的生活,在城市里到处闹事。小 猪iPig 为了更好地控制局面,他把城市改造成了另外一个样子:iPig 把道路全部摧毁之后重 新修建了m 条无向边,并且保证每一个小区最多存在于一个由无向边组成的环中。 iPig 以为这样做就让那些反和谐主义者不敢继续猖狂下去了,谁知到在新的城市道路修 建好以后反和谐主义者宣言要对城市的小区进行一次洗脑! 这下可麻烦了,iPig 赶紧收集了许多的情报。iPig 给每个小区标记了一个和谐值HX_i, 用它来表示第i 个小区的和谐程度。 通过地下消息iPig 又得知那些反和谐主义者进攻时有个规律:他们会选择若干个小区 下手,这些小区都派一只猪过去,把这些小区的和谐值归零。在这个过程中,每个选择的小 区所直接连接着的几个小区都派了一只猪去看守——以防被警猪给干扰。这个计划看似完美 但是还是存在一个漏洞:因为人员之间都是在网络上认识的,互相没有见过面,为了防止不 必要的麻烦(认错猪之类),每个小区最多只会有一头猪存在。 iPig 突然感到了莫大的压力,他想知道在最坏情况下会丢失多少和谐值。但是不懂计算 机的他不知道应该怎样计算。你能帮帮他吗?
【输入】 输入第一行有两个整数n 和m,表示pigsty 城市里面有n 个小区,在iPig 修整城市后 有m 条无向边连接着n 个小区。 接下来一行有n 个正整数,第i 个正整数HX_i 表示第i 个小区的和谐值为HX_i。 接下来m 行,每行两个正整数a 和b(1<=a,b<=n),表示存在一条连接着小区a 和小区 b 的无向边。
【输出】 输出只有一行一个整数,表示最坏情况下损失的和谐值为多少。
【样例输入】 9 9 2 2 3 4 1 2 3 10 11 1 2 2 3 1 3 3 5 5 4 5 6
4 7 6 7 8 9
【样例输出】 17
【样例解释】 反和谐主义者选择的小区分别是小区3(看守的小区是小区1、小区2 和小区5)、小区 7(看守的小区是小区4 和小区6)和小区9(看守的小区是小区8),这样会损失的总和谐 值为3+3+11=17。 或者选择的小区分别是小区1(看守的小区是小区2 和小区3)、小区4(看守的小区是 小区5 和小区7)和小区9(看守的小区是小区8),这样会损失的总和谐值为2+4+11=17。 如果同时选择小区3、小区4 和小区9,虽然损失的总和谐值为18,但是小区3 和小区 4 都要派猪来看守小区5,这不符合条件,故此方案不可行。
【数据约定】 对于20%的数据,保证每个点不存在于任何一个环中; 对于另外30%的数据,保证图中只存在一个环; 对于100%的数据,有N<=1000000,M<=2000000,所有的权值不超过1000。