时间限制:3s
内存限制:1024MB
假定你是李华。
作为一名优秀的文科生,你最近学习了电学。
你有 ∞ 个电荷量为 +e,动能足够大的点电荷,要将其中的一部分通入一个机器,并通出等量点电荷。最大化机器运作后电荷的动能之和。
机器可以看作 n 个节点,第 i 个点电势为 hiV。
第 i 个点有 pi 根管道可以从该点通入点电荷,在整个过程中每根管道最多通入一个点电荷,其中从第 j 根管道通入的点电荷会克服外力做 ai,jeV 的功。
第 i 个点有 qi 根管道可以从该点通出点电荷,在整个过程中每根管道最多通出一个点电荷,其中从第 j 根管道通出的点电荷会克服外力做 bi,jeV 的功。
机器内部有 m 条单向管道相连,第 i 条连接 ui 和 vi,表示可以将点电荷从 ui 运到 vi(没有次数限制),假定机器内其它力不做功,且你可以通过机器操纵每个点电荷的运动轨迹。
每个被通入的点电荷必须被通出,且机器内其它力不做功。即若一个点电荷从 x 点的第 i 根管道进入,从 y 点的第 j 根管道出去,机器对其做的功为(hx−hy−ax,i−by,j)eV
求最大的动能增加量之和(单位:eV)
输入格式
第一行两个正整数 n,m
接下来一行 n 个整数,第 i 个数为 hi。
接下来 m 行,每行两个正整数 ui,vi 描述一条单向管道。
接下来 n 行,第 i 行第一个正整数 pi,接下来 pi 个非负整数,第 j 个表示 ai,j
接下来 n 行,第 i 行第一个正整数 qi,接下来 qi 个非负整数,第 j 个表示 bi,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∼5:
见下发文件
数据范围
对于 100% 的数据,保证 1≤ui,vi≤n,0≤m,pi,qi,ai,j,bi,j,hi。其中 ai,j,bi,j,hi 均在对应范围内等概率随机,其余均以某种方式随机生成,不会针对性卡 spfa 等算法。
测试点编号 | n≤ | m≤ | pi,qi≤ | ai,j,bi,j< | hi< | 特殊性质 |
---|---|---|---|---|---|---|
1,2 | 50 | 200 | 10 | 10 | 30 | 无 |
3,4 | 70 | 300 | 100 | 100 | 2000 | |
5,6,7,8 | 100 | 500 | 200 | 200 | 104 | |
9,10 | 2000 | 5000 | 500 | 104 | 106 | A |
11,12,13,14 | n−1 | B | ||||
15,16,17,18 | 104 | C | ||||
19,20,21 | 700 | 5000 | 1000 | 106 | 108 | 无 |
22,23,24,25 | 2000 | 2×104 | 2000 |
特殊性质 A:|ui−vi|=1
特殊性质 B:m=n−1,ui<vi,vi=i+1
特殊性质 C:min
下发文件
由于本题的输入输出规模较大,额外下发一个IO板子。
该压缩包包含五个样例和一个IO板子。