bzoj#P3511. 土地划分

土地划分

题目描述

Y 国有 nn 座城市,并且有 mm 条双向公路将这些城市连接起来,并且任意两个城市至少有一条路径可以互达。

Y 国的国王去世之后,他的两个儿子 A 和 B 都想成为新的国王,但他们都想让这个国家更加安定,不会用武力解决问题。

于是他们想将这个国家分成两个小国家 A 国和 B 国。现在,A 拥有 11 号城市,B 拥有 nn 号城市,其他的城市还尚未确定归属哪边(划分之后的国家内部城市可以不连通)。

由于大家都想让国家变得更好,而某些城市的人民愿意国王的 A 儿子作为他们的领袖,而某些城市更看好 B,而为了交通的便捷,如果划分后的公路连接两个同一个国家的城市,那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制,具体如下:

  1. 对于城市 ii,如果它划分给 A 国,将得到 VA[i]VA[i] 的得分;划分给 B 国,将得到 VB[i]VB[i] 的得分。
  2. 对于一条公路 ii,如果它连接两个 A 国的城市,将得到 EA[i]EA[i] 的得分;连接两个 B 国的城市,将得到EB[i]EB[i] 的得分;否则,这条公路将失去意义,将扣除 EC[i]EC[i] 的得分。

现请你找到最优的土地划分,使得这种它的评分最高。

输入格式

第一行包含两个整数 n,mn,m,含义如问题描述所示。

接下来一行 n2n-2 个非负整数,表示 VA[2N1]VA[2 \dots N-1]

接下来一行 n2n-2 个非负整数,表示 VB[2N1]VB[2 \dots N-1]

接下来 mm 行,每行五个非负整数描述一条公路: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
11

样例说明

A 国仅有 11 号点,B 国有 22 号和 33 号点。

评分 =VB[2]+EB[2]EC[1]EC[3]=9+521=11=VB[2]+EB[2]-EC[1]-EC[3]=9+5-2-1=11

数据说明

数据点 nn mm 备注
121-2 20\le 20 200\le 200
343-4 5000\le 5000 10000\le 10000 VA,VB,EA,EBVA,VB,EA,EB 均为 00
565-6 ECEC 均为 00
7107-10 10000\le 10000 40000\le 40000

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