YZOJ P3049 [SHOI2010]Minimum Spanning Tree

时间限制：1000MS      内存限制：262144KB

难度：\(6.0\)

• 题目描述

有一个 \(n\) 个点，\(m\) 条边的无向图，每次可以对这张图进行操作：对于一条边 \((u,v)\)，可以把图中除了这条边以外的边，每一条的权值都减少 \(1\)。

对于某一条编号为 \(e\) 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？

• 输入格式

第一行输入三个整数 \(n\)、\(m\)、\(e\)。

接下来输入 \(m\) 行，每行输入三个整数，其中第 \(i+1\) 行输入的整数分别为 \(u_i\)、\(v_i\)、\(w_i\)，表示无向图的边的两个端点和边权。

• 输出格式

输出一个整数表示答案。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(50\%\) 的数据，\(n \leq 300\)，\(m \leq 1000\) 。

对于 \(100\%\) 的数据，\(n \leq 2 \times 10^4\)，\(m \leq 2 \times 10^5\)，\(0 \leq w_i \leq 2\times 10^4\) 。

 

 

 

---

 

 

 

考虑 Kruskal 算法，边 \(e\) 出现在最小生成树中，当且仅当权值比它小的边全部加进去时，仍然不能使得 \(e\) 的两端点连通。

所以就有了一个做法，把权值比它小的边全部弄成比它大，代价就是权值的差值，要割掉权值和尽量小的一些边，使得 \(e\) 的两端点不连通。

发现这是一个最小割模型。