Genghis Khan the Conqueror

题意翻译

### 题目大意: 有一个 $n$ 个点 $m$ 条边的无向图,每条边有边权。现有 $q$ 次修改,每次将从 $u$ 到 $v$ 的边的边权改为 $w$ 。问每次修改后该图最小生成树的边权和为多少。 **请在输入 $q$ 次修改后输出每次修改后答案的平均数,答案保留四位小数。** --- #### 输入格式: **本题有多组数据**。 对于每组数据: 第一行两个整数 $n,m$ ,表示 $n$ 个点 $m$ 条边。 接下来 $m$ 行,每行三个整数 $u,v,w$ ,表示这条边的端点 $u,v$ 以及边权 $w$ 。 第 $m+2$ 行一个整数 $q$ ,表示修改的总数。 接下来 $q$ 行,每行三个整数 $u,v,w$ ,表示将端点为 $u,v$ 的边的边权改为 $w$ 。 #### 输出格式: 对于每组数据: 输出一个浮点数,表示每次修改后最小生成树边权和的平均数。 --- #### 样例输入: ```plain 3 3 0 1 3 0 2 2 1 2 5 3 0 2 3 1 2 6 0 1 6 0 0 ``` #### 样例输出: ```plain 6.0000 ``` --- #### 样例解释: 修改前三次修改后最小生成树边权和分别为5,6,7,平均数为6。 ---- #### 数据范围: $1 \le n \leq 3000$,$1 \le m \le n^2$,$1\le q\le 10^4$。 $0 \le u,v \le n-1$,$w\le 10^7$。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4250 [PDF](https://uva.onlinejudge.org/external/15/p1504.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点