泊头市网站建设价格,wordpress留言的小伙伴,网站备案步骤,网站脑图用什么做题目描述 W 国的交通呈一棵树的形状。W 国一共有n - 1n−1个城市和nn个乡村#xff0c;其中城市从11到n - 1n−1 编号#xff0c;乡村从11到nn编号#xff0c;且11号城市是首都。道路都是单向的#xff0c;本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市#… 题目描述 W 国的交通呈一棵树的形状。W 国一共有n - 1n−1个城市和nn个乡村其中城市从11到n - 1n−1 编号乡村从11到nn编号且11号城市是首都。道路都是单向的本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市恰有一条公路和一条铁路通向这座城市。对于城市i 通向该城市的道路公路或铁路的起点要么是一个乡村要么是一个编号比ii大的城市。 没有道路通向任何乡村。除了首都以外从任何城市或乡村出发只有一条道路首都没有往 外的道路。从任何乡村出发沿着唯一往外的道路走总可以到达首都。 W 国的国王小 W 获得了一笔资金他决定用这笔资金来改善交通。由于资金有限小 W 只能翻修n - 1n−1条道路。小 W 决定对每个城市翻修恰好一条通向它的道路即从公路和铁 路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利于是根据人口调 查的数据小 W 对每个乡村制定了三个参数编号为ii的乡村的三个参数是a_iaib_ibi和c_ici。假设 从编号为ii的乡村走到首都一共需要经过xx条未翻修的公路与yy条未翻修的铁路那么该乡村 的不便利值为 c_i \cdot (a_i x) \cdot (b_i y)ci⋅(aix)⋅(biy) 在给定的翻修方案下每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修n - 1n−1条道路有很多方案其中不便利值最小的方案称为最优翻修方案小 W 自然 希望找到最优翻修方案请你帮助他求出这个最优翻修方案的不便利值。 输入格式 第一行为正整数nn。 接下来n - 1n−1行每行描述一个城市。其中第ii行包含两个数s_i,t_isi,ti。s_isi表示通向第ii座城市 的公路的起点t_iti表示通向第i座城市的铁路的起点。如果s_i 0si0那么存在一条从第s_isi座城 市通往第ii座城市的公路否则存在一条从第-s_i−si个乡村通往第i座城市的公路t_iti类似地如 果t_i 0ti0那么存在一条从第t_iti座城市通往第i座城市的铁路否则存在一条从第-t_i−ti个乡村通 往第ii座城市的铁路。 接下来nn行每行描述一个乡村。其中第i行包含三个数a_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 输入 #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 输入 #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 说明/提示 【样例解释 1】 如图所示我们分别用蓝色、黄色节点表示城市、乡村用绿色、红色箭头分别表示 公路、铁路用加粗箭头表示翻修的道路。 一种不便利值等于54的方法是翻修通往城市2和城市5的铁路以及通往其他城市的 公路。用→和⇒表示公路和铁路用∗→和∗⇒表示翻修的公路和铁路那么 编号为1的乡村到达首都的路线为-1 ∗→ 3 ⇒ 1经过0条未翻修公路和1条未翻修铁 路代价为3 × (1 0) × (2 1) 9编号为2的乡村到达首都的路线为-2 ⇒ 3 ⇒ 1经过0条未翻修公路和2条未翻修铁 路代价为2 × (1 0) × (3 2) 10编号为3的乡村到达首都的路线为-3 ∗→ 4 → 2 ∗→ 1经过1条未翻修公路和0条未 翻修铁路代价为3 × (2 1) × (1 0) 9编号为4的乡村到达首都的路线为-4 ⇒ 4 → 2 ∗→ 1经过1条未翻修公路和1条未翻 修铁路代价为1 × (2 1) × (3 1) 12编号为5的乡村到达首都的路线为-5 → 5 ∗⇒ 2 ∗→ 1经过1条未翻修公路和0条未 翻修铁路代价为2 × (3 1) × (1 0) 8编号为6的乡村到达首都的路线为-6 ∗⇒ 5 ∗⇒ 2 ∗→ 1经过0条未翻修公路和0条未翻修铁路代价为1 × (3 0) × (2 0) 6 总的不便利值为9 10 9 12 8 6 54。可以证明这是本数据的最优解。 【样例解释 2】 在这个样例中显然应该翻修所有公路。 【数据范围】 一共20组数据编号为1 ∼ 20。 对于编号\le 4≤4的数据n \le 20n≤20对于编号为5 ∼ 8的数据a_i,b_i,c_i \le 5ai,bi,ci≤5n \le 50n≤50对于编号为9 ∼ 12的数据n \le 2000n≤2000对于所有的数据n \le 20000n≤200001 \le a_i,b_i \le 601≤ai,bi≤601 \le c_i \le 10^91≤ci≤109s_i,t_isi,ti是[-n,-1] \cup (i,n - 1][−n,−1]∪(i,n− 转载于:https://www.cnblogs.com/xiongchongwen/p/11243470.html
