QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 4899. 机器

Statistics

时间限制:3s

内存限制:1024MB

假定你是李华。

作为一名优秀的文科生,你最近学习了电学。

你有 $∞$ 个电荷量为 $+e$,动能足够大的点电荷,要将其中的一部分通入一个机器,并通出等量点电荷。最大化机器运作后电荷的动能之和。

机器可以看作 $n$ 个节点,第 $i$ 个点电势为 $h_i \,\mathrm{V}$。

第 $i$ 个点有 $p_i$ 根管道可以从该点通入点电荷,在整个过程中每根管道最多通入一个点电荷,其中从第 $j$ 根管道通入的点电荷会克服外力做 $a_{i,j} \,\mathrm{eV}$ 的功。

第 $i$ 个点有 $q_i$ 根管道可以从该点通出点电荷,在整个过程中每根管道最多通出一个点电荷,其中从第 $j$ 根管道通出的点电荷会克服外力做 $b_{i,j} \,\mathrm{eV}$ 的功。

机器内部有 $m$ 条单向管道相连,第 $i$ 条连接 $u_i$ 和 $v_i$,表示可以将点电荷从 $u_i$ 运到 $v_i$(没有次数限制),假定机器内其它力不做功,且你可以通过机器操纵每个点电荷的运动轨迹。

每个被通入的点电荷必须被通出,且机器内其它力不做功。即若一个点电荷从 $x$ 点的第 $i$ 根管道进入,从 $y$ 点的第 $j$ 根管道出去,机器对其做的功为$(h_x−h_y−a_{x,i}−b_{y,j}) \,\mathrm{eV}$

求最大的动能增加量之和(单位:$\mathrm{eV}$)

输入格式

第一行两个正整数 $n,m$

接下来一行 $n$ 个整数,第 $i$ 个数为 $h_i$。

接下来 $m$ 行,每行两个正整数 $u_i,v_i$ 描述一条单向管道。

接下来 $n$ 行,第 $i$ 行第一个正整数 $p_i$,接下来 $p_i$ 个非负整数,第 $j$ 个表示 $a_{i,j}$

接下来 $n$ 行,第 $i$ 行第一个正整数 $q_i$,接下来 $q_i$ 个非负整数,第 $j$ 个表示 $b_{i,j}$

输出格式

输出一个非负整数表达答案。

样例

样例输入1:

3 4
3 9 2
1 1
2 3
3 3
3 2
1 2
1 0
1 2
1 1
1 2
1 1

样例输出 1:

6

样例$2\sim 5$:

见下发文件

数据范围

对于 $100\%$ 的数据,保证 $1\le u_i,v_i\le n$,$0\le m,p_i,q_i,a_{i,j},b_{i,j},h_i$。其中 $a_{i,j},b_{i,j},h_i$ 均在对应范围内等概率随机,其余均以某种方式随机生成,不会针对性卡 spfa 等算法。

测试点编号 $n\le$ $m\le $ $p_i,q_i\le$ $a_{i,j},b_{i,j}<$ $h_i<$ 特殊性质
$1,2$ $50$ $200$ $10$ $10$ $30$
$3,4$ $70$ $300$ $100$ $100$ $2000$
$5,6,7,8$ $100$ $500$ $200$ $200$ $10^4$
$9,10$ $2000$ $5000$ $500$ $10^4$ $10^6$ A
$11,12,13,14$ $n-1$ B
$15,16,17,18$ $10^4$ C
$19,20,21$ $700$ $5000$ $1000$ $10^6$ $10^8$
$22,23,24,25$ $2000$ $2\times 10^4$ $2000$

特殊性质 A:$|u_i−v_i|=1$

特殊性质 B:$m=n−1,u_i < v_i,v_i={i+1}$

特殊性质 C:$\min \{u_i,v_i\}≤4$

下发文件

由于本题的输入输出规模较大,额外下发一个IO板子。

该压缩包包含五个样例和一个IO板子。