#P9597. 浮动

    ID: 6208 传统题 1000ms 128MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-深度优先搜索Kahn 算法最小割建模Dinic最大流最小割定理

浮动

题目背景

“没时间,快决定。行动,还是再次停留。”——次祖伽密·凯尔

题意描述

第四隔离设施的防御阵地是一个 r×cr\times c 的网格。

相邻两个格子之间要么直接相连,要么有不可通过的墙相隔。

整个阵地中,任意两个位置有且仅有一条路径相连。

有 nn 太人形兵器把守该阵地,每个格子最多有一个人形兵器,经过该格子之前必须干掉格内的人形兵器。

每台人形兵器可以保护一个或几个人形兵器(可能包含自身)。人形兵器的火力很猛,尝试去攻击一个正在被保护的人形兵器无异于作死。而一个没有被保护的人形兵器则可以被轻易地干掉。

击杀一个人形兵器需要消耗一定的能量,而从其残骸上可以得到一定的能量补充。

现降落在 (x0,y0)(x_0,y_0) 并可以在任何地点脱身,要求获取尽可能多的能量。

你可以假设初始能量是足够多的。

输入格式

第一行四个数 r,c,x0,y0r, c, x_0, y_0,表示阵地大小和降落地点。

接下来 rr 行,每行 c−1c-1 个数,第 ii 行第 jj 个数表示 (i,j)(i, j) 与 (i,j+1)(i,j+1) 是否有墙相隔。

接下来 r−1r-1 行,每行 cc 个数,第 ii 行第 jj 个数表示 (i,j)(i,j) 与 (i+1,j)(i+1,j) 是否有墙相隔。

下一行两个数 n,mn,m,空格分隔,表示人形兵器的数量和保护关系的数量。

接下来 nn 行,每行 33 个数 xi,yi,wix_i, y_i, w_i,表示人形兵器坐标和攻击时带来的能量变化()负表示需要消耗,正表示可以得到补充)。

接下来 mm 行, 每行两个数 ai,bia_i,b_i,表示编号为 aia_i 的人形兵器保护编号为 bib_i 的人形兵器。

输入数据保证地图满足要求。注意所有坐标从 11 开始。

输出格式

仅一行,一个数,表示获取的最大能量值。

样例

6 4 1 1
1 1 0
1 0 0
0 0 0
1 1 0
0 1 0
0 1 0
0 0 1 0
0 0 1 1
1 0 0 1
0 0 1 0
1 0 0 1
7 2
3 1 3
1 3 -5
1 4 7
2 3 4
2 4 -2
4 2 -7
5 1 9
1 6
7 4
14

hCcmzF.png

看守关系:+3+3 看守 −7-7,+9+9 看守 +4+4。

攻击顺序:+3→−7→+9→+4→−2→+7+3\to -7\to +9\to +4\to -2\to +7,撤离。

数据规模与约定

对于 40%40\% 的数据,r,c≤15r,c\le 15,n≤15n\le 15,m≤30m\le 30,∣wi∣≤100|w_i|\le 100。

对于 100%100\% 的数据,1≤r,c≤1031\le r,c\le 10^3,0≤n≤1040\le n\le 10^4,1≤m≤3×1041\le m\le 3\times 10^4,∣wi∣≤104|w_i|\le 10^4。