UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3921. Mimori与树海

统计 下载数据

Description

Mimori知道了,只有毁灭掉神树,才能保护Yuuna和大家。但是,想要到神树那里需要穿越树海,树海非常危险,需要携带一定量的精灵才能通过。
她把树海抽象为一张有n个点和m条边的无向连通图,无重边和自环,结点编号为1~n,结点之间有双向道路连接。
每个结点有一个精灵需求数,u结点的精灵需求数记作w[u]。
通过这些边要支付一定数量的精灵!费用规定如下:
①若是普通道路(记作类别0),她需要支付1只精灵。
②若是特殊道路(记作类别1),她需要支付自己当前携带的精灵数的1/20,若不满20只则按20只计算。(例如、若她身上此时有10只精灵,则需要支付1只;若有69只精灵,则需要支付4只。)
她定义了一个整数S,令S等于每对结点之间的最优路径长度之和。我们用d(u,v)表示u,v之间的最优路径长度,d(u,v)被定义为从u沿路径到达v,且身上至少还有w[v]只精灵的前提下,初始携带的的最少精灵数(注意!仅仅在边上要支付精灵,在结点处不支付,但是你需要满足终点的精灵需求数)。(例如、结点数等于3时,S=d(1,1)+d(1,2)+d(1,3)+d(2,1)+d(2,2)+d(2,3)+d(3,1)+d(3,2)+d(3,3))
那么问题来了,她想删除一条边后使得新的S值S’最大。当然,你必须保证删除后图仍然连通才行。

Input

第一行包括2个整数n,m,分别表示图的顶点数和边数。
第二行包括n个整数w1...wn,表示n个结点的精灵需求数。
接下来m行,每行包括三个整数u,v,op,代表一条连接u、v的无向边,其类别为op(参见题目描述)。
保证图连通,且无重边和自环。

Output

仅包含一行,包括2个整数,为S和最大的S’。

Sample Input

5 6
15 14 10 14 12
1 2 0
2 3 0
3 4 1
2 5 1
3 5 1
3 1 1

Sample Output

353 357

Hint

1<=n<=110,

1<=m<=1100,

1<=u<=n,

1<=v<=n,u≠v,

0<=op<=1,

1<=wi<=100(1<=i<=n),

保证图连通,且无重边和自环。


Source