YZOJ P1868 土地划分
时间限制:1000MS 内存限制:131072KB
难度:\(5.1\)
在 \(Y\) 国有 \(N\) 座城市,并且有 \(M\) 条双向公路将这些城市连接起来,并且任意两个城市至少有一条路径可以互达。\(Y\) 国的国王去世之后,他的两个儿子 \(A\) 和 \(B\) 都想成为新的国王,但他们都想让这个国家更加安定,不会用武力解决问题。于是他们想将这个国家分成两个小国家 \(A\) 国和 \(B\) 国。现在,\(A\) 拥有 \(1\) 号城市,\(B\) 拥有 \(N\) 号城市,其他的城市还尚未确定归属哪边。
由于大家都想让国家变得更好,而某些城市的人民愿意国王的 \(A\) 儿子作为他们的领袖,而某些城市更看好 \(B\),而为了交通的便捷,如果划分后的公路连接两个同一个国家的城市,那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制,具体如下:
1,对于城市 \(i\) ,如果它划分给 \(A\) 国,将得到 \(VA[i]\) 的得分;划分给 \(B\) 国,将得到 \(VB[i]\) 的得分。
2,对于一条公路 \(i\) ,如果它连接两个 \(A\) 国的城市,将得到 \(EA[i]\) 的得分;连接两个 \(B\) 国的城市,将得到 \(EB[i]\) 的得分;否则,这条公路将失去意义,将扣除 \(EC[i]\) 的得分。
现请你找到最优的土地划分,使得这种它的评分最高。
第一行包含两个整数 \(N\),\(M\),含义如问题描述所示。
接下来一行 \(N-2\) 个非负整数,表示 \(VA[2..N-1]\) 。
接下来一行 \(N-2\) 个非负整数,表示 \(VB[2..N-1]\) 。
接下来 \(M\) 行,每行五个非负整数描述一条公路:\(X, Y, EA[i], EB[i], EC[i]\),含义如问题描述所示。
输出一个整数,表示最高评分。
|
3 3 8 9 1 2 2 6 2 2 3 8 5 7 1 3 9 4 1 |
\(100\%\) 的数据 \(N \leq 10000, M \leq 40000\);
保证运算过程中及最终结果不超过32位带符号整数类型的表示范围。…
Read the rest