OpenJudge

E06T01:在线更新MST

总时间限制:
1000ms
内存限制:
65536kB
描述

给定无向图G(V,E),求其MST的值。之后,在图中加入一条新边,更新MST的值。

输入
第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N <= 5000,M <= 100000)
接下来M行,每行包含3个整数{u,v,w},表示一条权值为w的无向边 (u,v)

第M+2行,包含一个整数T,代表共加入T条新边(T<=2000)
之后T行,每行包含3个整数{u,v,w},表示一条权值为w的无向边 (u,v)
输出
第一行,输出原图MST的值。
之后T行,依次输出每加入1条新边之后的MST值。
样例输入
3 3
1 2 5
1 3 6
2 3 7
2
2 3 1
1 3 1
样例输出
11
6
2
全局题号
15375
添加于
2017-09-09
提交次数
1
尝试人数
1
通过人数
0