| 比赛场次 | 303 |
|---|---|
| 比赛名称 | 20160415 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2016-04-15 08:20:00 |
| 结束时间 | 2016-04-15 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 能量网络 |
|---|---|
| 输入输出 | energynet.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 _Horizon |
AAAAAAAAAA | 0.722 s | 7.09 MiB | 100 |
 前鬼后鬼的守护 |
AAAAAAATTT | 3.113 s | 0.78 MiB | 70 |
 collor |
WAAAAWWAAW | 0.100 s | 4.88 MiB | 60 |
 mikumikumi |
WAAAAWWWWW | 0.138 s | 0.31 MiB | 40 |
 lxtgogogo |
AAAWWWWWWW | 0.102 s | 3.80 MiB | 30 |
 dydxh |
AAAWWWWWWW | 0.395 s | 4.87 MiB | 30 |
 debug |
AAAWWWWWWW | 0.443 s | 0.95 MiB | 30 |
 Satoshi |
AAAEEEEEEE | 0.640 s | 0.32 MiB | 30 |
 KZNS |
AWWWWWWWWW | 0.033 s | 0.35 MiB | 10 |
 sro_lzh_mzx_dydx |
WWWWWWWWWW | 0.002 s | 0.31 MiB | 0 |
 WAHT |
WWWWWWWWWW | 0.017 s | 0.76 MiB | 0 |
 TZJerry |
WWWWWWWWWW | 0.043 s | 7.98 MiB | 0 |
 sro dydxh orz |
WWWWWWWWWW | 0.071 s | 0.90 MiB | 0 |
 Fmuckss |
TTTWWWWWWW | 3.025 s | 3.02 MiB | 0 |
 咸鱼二号 |
WWWTTTTTTT | 7.005 s | 1.10 MiB | 0 |
 FETS 1/3 |
TTTTTTTTTT | 10.003 s | 10.26 MiB | 0 |
【题目描述】
现在有N个点M条有向边组成能源网络图。每一个结点有一个初始值Ai，表示第i个结点可以提供的额外能源供给。
如果结点x到结点y有一条有向边，那么就意味着结点x的需要结点y传输能源。结点x会挑选由它出发的边的终点中，权值最大的点（假设为y）作为能源供给点，花费的代价就是Ay： Wx=max{Ay} Ay必须满足x到y存在一条有向边。
也就是说补充能源x结点的花费为x结点连接的所有终点y中Ay的最大值。
当然，作为能源提供者的某些点，还可以选择花费额外的Bi的花费将此结点的Ai清为0。
而你现在就要计算一下这个能源网络图所有传输能源的最小花费。
【输入格式】
第一行两个整数N和M
第二行N个整数，A1,A2……AN
第三行N个整数，B1,B2……BN
接下来M行，每行两个整数xj和yj，表示存在xj到yj的一条有向边。
【输出格式】
一个整数，保证这个能源网络图正常运营的最小花费。
【样例输入】
2 1
100000 10000
100000 1
1 2
【样例输出】
1
【提示】
最优方案是花费1的费用将A2改为0。
【数据范围】
30% N<=20
100% 1<=N<=1000 0<=M<=50000 0<=Ai<50000 0<=Bi<=10000
【来源】
在此键入。