Skip to content

1013: 抗震救灾

题目

题目描述

近日,由于一场世纪大地震,某国通讯设施全面瘫痪。在灾后重建中,抢修通讯设备成为首要任务。现在,你已经了解该国的基本状况,该国首脑希望你设计一种方案,使得所用的救灾资金尽可能少。

已知该国地形可以简化成包含$n$个点的一张无向图,每个点代表一座城市。由于地震的破坏,该国的城市之间已经只剩下$m$条仍具备通行条件的双向道路。当然,目前该国的所有城市是联通的。现在,该国希望在一些仍能通行的道路下铺设通信电缆,使得任意两个城市之间能够通过通信电缆直接或间接地传递灾情。不过,若某条道路被破坏后,该国的所有城市不再全部联通,则这条道路被认为是危险道路,因为一旦这条道路被次生灾害破坏,那么相应的通信电缆也会被破坏,而且没有其他可供选择的途径来恢复通信。在这样的危险道路上,你只能选择用无线通信设备代替。(注意:在非危险道路上,即使无线设施的费用低于通信电缆的费用,你也只能铺设通信电缆,因为这种方式可靠性更高。)

输入格式

第一行包含两个正整数$n$和$m$。

接下来共$m$行,第$i$行包含四个整数$s_i$,$t_i$,$a_i$和$b_i$,分别表示第$i$条道路连接的两座城市,以及在该条道路上铺设电缆和架设无线设备的费用。

输出格式

第一行包含一个整数,表示最小代价。

样例输入

8 11 2 6 0 9 2 7 8 6 7 3 4 0 4 8 3 0 4 5 0 0 4 1 1 10 2 4 0 10 7 6 0 10 2 3 2 1 1 4 1 0 1 5 2 4

样例输出

13

数据范围

  • 对于$30\%$的数据,$n \le 500$,$m \le 3000$。
  • 对于额外$40\%$的数据,数据保证不存在危险道路。
  • 对于$100\%$的数据,$n \le 10^{5}$,$m \le 5 \times 10^{5}$。
  • 在每一部分数据中,均包含若干较小的测试点。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!