#P17862. [XV Open Cup]Steiner Tree in Random Graph

[XV Open Cup]Steiner Tree in Random Graph

题目描述

给定一个有 nn 个顶点的无向带权图。编号为 1,2,…,n−k1,2,\ldots,n-k 的顶点必须被包含,其余顶点可以自由选择是否使用。

请选出一个连通子图,使它包含所有必选顶点,并且所选边的权值总和最小。你需要输出这个子图的边。如果存在多个最优答案,输出任意一个。

输入生成条件是本题的一部分。 除样例外,所有测试数据均按照以下方式生成:

  1. 由出题者选择参数 n,m,kn,m,k。
  2. 将 n(n−1)/2n(n-1)/2 条可能的无向边随机排列,并依次考虑。
  3. 当且仅当加入当前边后,仍能通过加入零条或若干条尚未考虑的边,得到一个总边数不超过 mm 的连通图时,加入当前边。
  4. 对每条加入的边,独立地从整数区间 [50,100][50,100] 中均匀选择权值。

不要把本题理解为需要在给定时间内解决任意构造的斯坦纳树实例。

输入格式

第一行包含三个整数 n,m,kn,m,k。

接下来 mm 行,每行包含三个整数 ai,bi,wia_i,b_i,w_i,表示一条连接 ai,bia_i,b_i、权值为 wiw_i 的无向边。

图没有自环和重边。

输出格式

第一行输出一个非负整数 cc,表示选出的边数。

接下来 cc 行,每行输出一条所选边的两个端点。端点顺序、边的输出顺序均任意。

所选边必须来自输入,不能重复。所有被选边涉及的顶点以及所有必选顶点必须属于同一个连通子图。

若只有一个必选顶点,可以只选该顶点而不选边,此时输出 0。若必选顶点集合为空,同样输出 0。

数据范围

  • 5≤n≤1005\le n\le100;
  • 2n≤m≤10n2n\le m\le10n,且因图为简单图,m≤n(n−1)/2m\le n(n-1)/2;
  • 0≤k≤300\le k\le30;
  • 1≤ai<bi≤n1\le a_i<b_i\le n;
  • 50≤wi≤10050\le w_i\le100。

必选顶点集合准确地指 {v∣1≤v≤n−k}\{v\mid1\le v\le n-k\}。本题包生成的非样例数据均至少包含一个必选顶点。

样例 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 中,选择可选顶点 55 后可以得到总权值为 53+51+56=16053+51+56=160 的最优子图。