题目描述
给定一个 n 个点 m 条边的带权图,每条边的边权为 wi ,有两种询问。
1.求其最小方差生成树。
2.对于每条边,问如果删除它,残余图(包含 n 个点 m−1 条边)的最小方差生成树。
你只需要求出最小的方差值。如果图不连通,输出 −1。
一个生成树的方差定义为它的所有边的权值的方差。
对于 N 个变量 x1,x2...xN,其方差计算方式为 σ2=N∑1≤i≤N(xi−μ)2
其中 σ2 为方差,μ 为平均值,由于是生成树,所以 N=n−1。
你需要将方差乘 N2 后输出,可以证明这是一个整数。
输入格式
第 1 行包含 3 个整数 n,m,T,表示点数,边数和询问类型。
接下来 m 行,每行包含 3 个正整数 ui,vi,wi ,表示第 i 条边连接 ui 和 vi ,权值为 wi ,保证无自环,但可能有重边。
输出格式
当 T=1,输出一个数表示答案。
当 T=2,输出 m 行,每行一个数表示删除第 i 条边的答案。
如果图不连通,输出-1。
样例
4 4 2
1 2 1
2 3 3
1 3 2
3 4 5
14
26
24
-1
数据范围与提示
子任务 |
分值 |
T |
n≤ |
m≤ |
C≤ |
1 |
5 |
1 |
m |
20 |
106 |
2 |
10 |
200 |
3 |
1000 |
104 |
4 |
106 |
5 |
105 |
109,且满足特性 1 |
6 |
15 |
109 |
7 |
20 |
2 |
300 |
106 |
8 |
1018 |
特性1:第 i 条边连接点 (imodn)+1 和点 ((i+1)modn)+1,且 wi≤wi+1。