Codeforces 125E MST Company

最近队长让我看图论问题，顺便从现在开始练习简述问题。第一道用来开刀的是 Codeforces 125E.

原题地址：http://codeforces.com/problemset/problem/125/E

题目大意是有 n 个城市，m 条毁坏了的道路，1 号城市是首都。现在要在这个图中重建道路，使得每个城市都能连通。但是还有一个要求，就是连向首都的路必须是 k 条。修路有代价，求最小代价。

这个问题非常类似 MST, 不然怎么又叫 MST Company 呢？

我的想法是，先考虑首都，首先把连向首都的路都找出来，然后选择其中 k 个最小的路，在此基础上做 MST 就可以了。

目前没 AC, 没写代码，不能保证思路的正确性。

输入数据第一行有 3 个数，就是 n, m, k. 然后接下来 m 行每行有 3 个数，记为 a, b, w, 表示从城市 a 到城市 b 可以修路，代价是 w. 样例如下：

4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2

输出是先输出一个数，表示要修几条路，然后换行，输出这些路在输入数据中排列的序号。样例如下：

3
1 5 2

添加于 2011-11-03 18:53:00 …

今天听队长 Wideas 说，别人 AC 的代码不是这样做的。他们是先把所有连向首都的边都先加上了一个数，设为 w, 这个 w 可以是负数。然后，用二分法确定 w 的值，每次都做一次最小生成树。直到做的结果刚好能让连向首都的 k 条边在最小生成树里就可以了。

目前我也没有找到我原来思路的反例（我也没有怎么找），但是如果思路像我原来想的那么简单的话，怎么会才这么点人 AC 呢？然而感觉后来这种算法也有问题，会不会在选连向首都的路的时候，不管那些路加上的 w 是多少，都没有办法生成一个最小生成树，使得边数是 k 呢？就是说，可能 w 小一点，就会选到 k + 1 条边，w 大一点又只能选到 k – 1 条边这样的情况……