#P17862. [XV Open Cup]Steiner Tree in Random Graph
[XV Open Cup]Steiner Tree in Random Graph
题目描述
给定一个有 个顶点的无向带权图。编号为 的顶点必须被包含,其余顶点可以自由选择是否使用。
请选出一个连通子图,使它包含所有必选顶点,并且所选边的权值总和最小。你需要输出这个子图的边。如果存在多个最优答案,输出任意一个。
输入生成条件是本题的一部分。 除样例外,所有测试数据均按照以下方式生成:
- 由出题者选择参数 。
- 将 条可能的无向边随机排列,并依次考虑。
- 当且仅当加入当前边后,仍能通过加入零条或若干条尚未考虑的边,得到一个总边数不超过 的连通图时,加入当前边。
- 对每条加入的边,独立地从整数区间 中均匀选择权值。
不要把本题理解为需要在给定时间内解决任意构造的斯坦纳树实例。
输入格式
第一行包含三个整数 。
接下来 行,每行包含三个整数 ,表示一条连接 、权值为 的无向边。
图没有自环和重边。
输出格式
第一行输出一个非负整数 ,表示选出的边数。
接下来 行,每行输出一条所选边的两个端点。端点顺序、边的输出顺序均任意。
所选边必须来自输入,不能重复。所有被选边涉及的顶点以及所有必选顶点必须属于同一个连通子图。
若只有一个必选顶点,可以只选该顶点而不选边,此时输出 0。若必选顶点集合为空,同样输出 0。
数据范围
- ;
- ,且因图为简单图,;
- ;
- ;
- 。
必选顶点集合准确地指 。本题包生成的非样例数据均至少包含一个必选顶点。
样例 1
5 10 3
1 2 50
1 3 51
1 4 52
1 5 53
2 3 54
2 4 55
2 5 56
3 4 57
3 5 58
4 5 59
1
1 2
样例 2
5 10 2
1 2 100
1 3 100
1 4 57
1 5 56
2 3 100
2 4 54
2 5 53
3 4 52
3 5 51
4 5 50
3
5 2
5 3
1 5
样例解释
样例 2 中,选择可选顶点 后可以得到总权值为 的最优子图。