7921: BZOJ3921：Mimori与树海

Mimori知道了，只有毁灭掉神树，才能保护Yuuna和大家。但是，想要到神树那里需要穿越树海，树海非常危险，需要携带一定量的精灵才能通过。 她把树海抽象为一张有n个点和m条边的无向连通图，无重边和自环，结点编号为1~n，结点之间有双向道路连接。 每个结点有一个精灵需求数，u结点的精灵需求数记作w。 通过这些边要支付一定数量的精灵！费用规定如下： ①若是普通道路(记作类别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’最大。当然，你必须保证删除后图仍然连通才行。

输入格式

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

输出格式

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

样例输入

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

样例输出

353 357

提示

1<=n<=110， 1<=m<=1100， 1<=u<=n， 1<=v<=n，u≠v， 0<=op<=1， 1<=wi<=100(1<=i<=n)， 保证图连通，且无重边和自环。

题目来源

没有写明来源