#P3511. 土地划分

    ID: 2723 传统题 1000ms 256MiB 尝试: 334 已通过: 140 难度: 7 上传者: 标签>难度分类提高+/省选-图论最小割建模Dinic当前弧优化最大流最小割定理CF2200

土地划分

土地划分

题目描述

Y 国有 nn 座城市和 mm 条双向公路,任意两座城市都能经由公路到达。王位继承人 A 和 B 决定将领土一分为二。城市 11 归 A 国,城市 nn 归 B 国。其余城市各划给其中一个国家,划分后每个国家内的城市可以不连通。

总评分按以下规则计算。

  • 对于城市 ii(2≤i≤n−12\le i\le n-1),划给 A 国获得 VAiVA_i 分,划给 B 国获得 VBiVB_i 分。城市 11 和 nn 没有单独的评分。
  • 对于第 ii 条公路,两端都在 A 国时获得 EAiEA_i 分,两端都在 B 国时获得 EBiEB_i 分,分属两国时扣除 ECiEC_i 分。

求最高总评分。

输入格式

第一行有两个整数 n,mn,m。

第二行有 n−2n-2 个非负整数 VA2,…,VAn−1VA_2,\ldots,VA_{n-1}。第三行有 n−2n-2 个非负整数 VB2,…,VBn−1VB_2,\ldots,VB_{n-1}。

接下来 mm 行,第 ii 行有五个整数 xi,yi,EAi,EBi,ECix_i,y_i,EA_i,EB_i,EC_i,表示一条连接城市 xi,yix_i,y_i 的公路及其三种评分参数。公路两端的编号在 11 到 nn 之间,三个评分参数均为非负整数。

输出格式

输出一行一个整数,表示最高总评分。

样例 #1

3 3
8
9
1 2 2 6 2
2 3 8 5 7
1 3 9 4 1
11

城市 22 划给 B 国时,总评分为 VB2+EB2−EC1−EC3=9+5−2−1=11VB_2+EB_2-EC_1-EC_3=9+5-2-1=11。

数据范围

测试点 nn 的上限 mm 的上限 附加条件
1–2 2020 200200 无
3–4 50005000 1000010000 所有 VAi,VBi,EAi,EBiVA_i,VB_i,EA_i,EB_i 均为 00
5–6 所有 ECiEC_i 均为 00
7–10 1000010000 4000040000 无

题目保证评分的运算过程和最终结果均在 32 位有符号整数范围内。