#1759. 最小方差生成树

    ID: 1759 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest126来源:qoj.ac数据:公开样例最小生成树

最小方差生成树

最小方差生成树

题目描述

标题: 最小方差生成树 - Problem - QOJ.ac

#4784. 最小方差生成树

Statistics

The problem was used in the following contests:

给定一个 n 个点 m 条边的带权图,每条边的边权为 wi ,有两种询问。

  1. 求其最小方差生成树。
  2. 对于每条边,问如果删除它,残余图(包含 n 个点 m−1 条边)的最小方差生成树。

你只需要求出最小的方差值。如果图不连通,输出 −1。

一个生成树的方差定义为它的所有边的权值的方差。

对于 N 个变量 x1,x2...xN,其方差计算方式为 σ2=∑1≤i≤N(xi−μ)2N

其中 σ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 10 1000 104 4 10 106 5 10 105 109,且满足特性 1 6 15 109 7 20 2 300 106 8 20 1018

特性1:第 i 条边连接点 (imodn)+1 和点 ((i+1)modn)+1,且 wi≤wi+1。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 4 2
1 2 1
2 3 3
1 3 2
3 4 5
14
26
24
-1