Problem1074--#2138. 「ZJOI2015」醉熏熏的幻想乡

1074: #2138. 「ZJOI2015」醉熏熏的幻想乡

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

傲娇少女幽香是一个很萌很萌的妹子,这些天幻想乡的大家都不知道为何还是拼命喝酒。很快酒就供不应求了,为了满足大家的需求,幽香决定在森林里酿酒。

经过调查,幽香发现森林里面有一些地方非常适合酿酒,有一些地方则非常适合存酒。
幽香把这些适合酿酒的地方称为酿酒点,不妨认为有 nnn 个酿酒点,从 111nnn 标号。
同时也有 mmm 个适合存酒的地方,幽香将它们称为存酒点,从 111mmm 标号。
在一些酿酒点和存酒点之间存在通道,如果酿酒点 iii 到存酒点 jjj 之间存在通道,那么 iii 生产的酒就可以被运输到 jjj

但是在一个地方酿酒是需要消耗幽香的魔力的,由于存在管理上的因素,在酿酒点 iii,制造 xxx 升的酒,需要花费 aix2+bixa_ix^2+b_ixaix2+bix 的魔力,注意 xxx 不一定是一个非负整数,也可以是一个非负实数,同时在这个点最多只能制造 cic_ici 升的酒。

每个存酒点 jjj 有一个容量 djd_jdj,表示这个存酒点最多能存多少升的酒。幽香打算存尽量多的酒,那么她需要在一些酿酒点生产一些酒并且通过通道将酒运送到存酒点。

当然幽香想要节省自己的魔力,所以想让你帮忙算出在满足要求的情况下,最少花费的魔力是多少?

输入格式

第一行两个正整数 n,mn,mn,m,表示酿酒点和存酒点的数量。
接下来 nnn 行,第 iii 行三个数 ai,bi,cia_i,b_i,c_iai,bi,ci,表示在酿酒点i制造酒的花费系数,和上限。
接下来一行 mmm 个整数,依次为每个存酒点的 did_idi 值。
接下来 nnn 行,每行 mmm 个数,其中第 iii 行第 jjj 个表示酿酒点 iii 到存酒点 jjj 有没有通道(111 表示有,000 表示没有)。

输出格式

输出第一行表示幽香最多能存多少升酒(注意这肯定是个整数,直接输出即可)。
输出一行表示最小花费魔力,注意这肯定是一个有理数,化简后按照 a/b 的形式输出(000 输出 0/1)。

样例

样例输入

10 10
0 2 3
2 3 2
3 1 3
1 2 1
1 0 1
1 1 0
3 3 0
1 2 2
3 1 1
3 1 0
3 1 2 2 3 1 1 2 2 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0
1 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0

样例输出

8
42/1

数据范围与提示

对于 30%30 \%30% 的数据:所有 ai=0a_i=0ai=0
对于另 30%30 \%30% 的数据:最终答案的分母≤1000\leq 10001000
对于 100%100 \%100% 的数据:1≤n≤100, 1≤m≤1001 \leq n \leq 100, \ 1 \leq m \leq 1001n100, 1m100
对于所有数据,0≤ai,bi,ci,di≤30 \leq a_i,b_i,c_i,d_i \leq 30ai,bi,ci,di3且都是整数。同时对于每个 iiiai+bi>0a_i+b_i>0ai+bi>0 通道的数量不超过 100010001000 条。
非常神奇的是,对于所有数据存在一个正整数 X≤107X \leq 10^7X107,使得存在一个最优解,使得所有路径上运送的酒的体积都是 1/X1/X1/X 的倍数。

Source/Category