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]\)，含义如问题描述所示。

• 输出格式

输出一个整数，表示最高评分。

• 样例输入

• 样例输出

• 数据规模与约定

\(100\%\) 的数据 \(N \leq 10000, M \leq 40000\)；

保证运算过程中及最终结果不超过32位带符号整数类型的表示范围。

 

 

Source: BZOJ 3511

---

 

 

 

听说是贾教流的模板题？？？

传说中的论文：浅析一类最小割问题(pty).pdf

其实我不是很看得懂 QAQ（太菜

还有一种奇怪的做法：

\(S\) 向 \(1\) 连 \(\infty\) 的边，\(N\) 向 \(T\) 连 \(\infty\) 的边。

\(S\) 向 \(i\) 连 \(VA_i\) 的边，\(i\) 向 \(T\) 连 \(VB_i\) 的边。

对于原图中的一条边 \(i, \; x \leftrightarrow y\) ：新建一个点 \(NA\) ，\(S\) 向 \(NA\) 连 \(EA_i+EC_i\) 的边，\(NA\) 分别向 \(x, y\) 连 \(\infty\) 的边；再新建一个点 \(NB\) ，\(NB\) 向 \(T\) 连 \(EB_i+EC_i\) 的边，\(x, y\) 分别向 \(NB\) 连 \(\infty\) 的边。

跑最小割，取没有被割掉的边权（指权值中 \(VA,VB,EA,EB\) 的部分），最后加上 \(\sum {EC}\) 就是本题的答案。

 

假设原图中的点有 \(1,2,3,N\) ，边有 \(2 \leftrightarrow 3, 3 \leftrightarrow N\) ，那么建出来的图是这样的：

（注：图中未注明边权的为 \(\infty\)）

 

若同时割掉 \(VA_2, VB_3\)（或 \(VA_3, VB_2\)），那么有

要使 \(S \rightarrow T\) 不连通，必须同时割掉 \(EA+EC, EB+EC\) ，对真正答案贡献了 \(VA_3+VB_2-EC\)（或 \(VA_2+VB_3-EC\)） 。

 

若同时割掉 \(VA_2, VA_3\)，那么有

要使 \(S \rightarrow T\) 不连通，必须割掉 \(EA+EC\) ，对真正答案贡献了 \(VB_2+VB_3+EB\) 。

 

若同时割掉 \(VB_2, VB_3\)，那么有

要使 \(S \rightarrow T\) 不连通，必须割掉 \(EB+EC\) ，对真正答案贡献了 \(VA_2+VA_3+EA\) 。

 

以此类推，可证其正确性。

就是点数变成 \(N+2M\) 有点慢而已。