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)