#2510. 「AHOI / HNOI2018」道路

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

W 国的交通呈一棵树的形状。W 国一共有 n1 个城市和 nnn 个乡村,其中城市从 111n1 编号,乡村从 111nnn 编号,且 111 号城市是首都。道路都是单向的,本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市,恰有一条公路和一条铁路通向这座城市。对于城市 iii,通向该城市的道路(公路或铁路)的起点,要么是一个乡村,要么是一个编号比 iii 大的城市。没有道路通向任何乡村。除了首都以外,从任何城市或乡村出发只有一条道路;首都没有往 外的道路。从任何乡村出发,沿着唯一往外的道路走,总可以到达首都。

W 国的国王小 W 获得了一笔资金,他决定用这笔资金来改善交通。由于资金有限,小 W 只能翻修 n1 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路,即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利,于是根据人口调查的数据,小 W 对每个乡村制定了三个参数,编号为 iii 的乡村的三个参数是 aia_iaibib_ibicic_ici。假设从编号为 iii 的乡村走到首都一共需要经过 xxx 条未翻修的公路与 yyy 条未翻修的铁路,那么该乡村的不便利值为

ci⋅(ai+x)⋅(bi+y)c_i \cdot (ai + x) \cdot (bi + y)ci(ai+x)(bi+y)

在给定的翻修方案下,每个乡村的不便利值相加的和为该翻修方案的不便利值。

翻修 n1 条道路有很多方案,其中不便利值最小的方案称为最优翻修方案,小 W 自然希望找到最优翻修方案,请你帮助他求出这个最优翻修方案的不便利值。

输入格式

第一行为正整数 nnn。 接下来 n1 行,每行描述一个城市。其中第 iii 行包含两个数 si,tis_i, t_isi,tisis_isi 表示通向第 iii 座城市的公路的起点,tit_iti 表示通向第 iii 座城市的铁路的起点。如果 si>0s_i > 0si>0,那么存在一条从第 sis_isi 座城市通往第 iii 座城市的公路,否则存在一条从第 −si-s_isi 个乡村通往第 iii 座城市的公路;tit_iti 类似地,如果 ti>0t_i > 0ti>0,那么存在一条从第 tit_iti 座城市通往第 iii 座城市的铁路,否则存在一条从第 −ti-t_iti 个乡村通往第 iii 座城市的铁路。

接下来 nnn 行,每行描述一个乡村。其中第 iii 行包含三个数 ai,bi,cia_i, b_i, c_iai,bi,ci,其意义如题面所示。

输出格式

输出一行一个整数,表示最优翻修方案的不便利值。

样例

样例输入 1

6
2 3
4 5
-1 -2
-3 -4
-5 -6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

样例输出 1

54

样例解释 1

样例.png

如图所示,我们分别用蓝色、黄色节点表示城市、乡村;用绿色、红色箭头分别表示公路、铁路;用加粗箭头表示翻修的道路。

一种不便利值等于 545454 的方法是:翻修通往城市 222 和城市 555 的铁路,以及通往其他城市的公路。用→\rightarrow⇒\Rightarrow表示公路和铁路,用表示翻修的公路和铁路,那么:

  • 编号为 111 的乡村到达首都的路线为:131,经过 000 条未翻修公路和 111 条未翻修铁路,代价为 3×(1+0)×(2+1)=93 \times (1 + 0) \times (2 + 1) = 93×(1+0)×(2+1)=9
  • 编号为 222 的乡村到达首都的路线为:231,经过 000 条未翻修公路和 222 条未翻修铁路,代价为 2×(1+0)×(3+2)=102 \times (1 + 0) \times (3 + 2) = 102×(1+0)×(3+2)=10
  • 编号为 333 的乡村到达首都的路线为:3421,经过 111 条未翻修公路和 000 条未翻修铁路,代价为 3×(2+1)×(1+0)=93 \times (2 + 1) \times (1 + 0) = 93×(2+1)×(1+0)=9
  • 编号为 444 的乡村到达首都的路线为:4421,经过 111 条未翻修公路和 111 条未翻修铁路,代价为 1×(2+1)×(3+1)=121 \times (2 + 1) \times (3 + 1) = 121×(2+1)×(3+1)=12
  • 编号为 555 的乡村到达首都的路线为:5521,经过 111 条未翻修公路和 000 条未翻修铁路,代价为 2×(3+1)×(1+0)=82 \times (3 + 1) \times (1 + 0) = 82×(3+1)×(1+0)=8
  • 编号为 666 的乡村到达首都的路线为:6521,经过 000 条未翻修公路和 000 条未翻修铁路,代价为 1×(3+0)×(2+0)=61 \times (3 + 0) \times (2 + 0) = 61×(3+0)×(2+0)=6

总的不便利值为 9+10+9+12+8+6=549 + 10 + 9 + 12 + 8 + 6 = 549+10+9+12+8+6=54。可以证明这是本数据的最优解。

样例输入 2

9
2 -2
3 -3
4 -4
5 -5
6 -6
7 -7
8 -8
-1 -9
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1

样例输出 2

548

样例解释 2

在这个样例中,显然应该翻修所有公路。

样例输入 3

12
2 4
5 3
-7 10
11 9
-1 6
8 7
-6 -10
-9 -4
-12 -5
-2 -3
-8 -11
53 26 491
24 58 190
17 37 356
15 51 997
30 19 398
3 45 27
52 55 838
16 18 931
58 24 212
43 25 198
54 15 172
34 5 524

样例输出 3

5744902

数据范围与提示

202020 组数据,编号为 120

对于编号 ≤4\le 44 的数据,n≤20n \le 20n20

对于编号为 58 的数据,ai,bi,ci5n50

对于编号为 912 的数据,n≤2000n \le 2000n2000

对于所有的数据,n≤20000n \le 20000n200001≤ai,bi≤601 \le a_i, b_i \le 601ai,bi601≤ci≤1091 \le c_i \le 10^91ci109si,tis_i, t_isi,ti[n,1](i,n1] 内的整数,任意乡村可以通过不超过 404040 条道路到达首都。