2047. [ZOJ 2676]网络战争

【题目描述】

Byteland的网络是由n个服务器和m条光纤组成的，每条光纤连接了两个服务器并且可以双向输送信息。这个网络中有两个特殊的服务器，一个连接到了全球的网络，一个连接到了总统府，它们的编号分别是1和N.

最近一家叫做Max Traffic的公司决定控制几条网络中的光纤，以使他们能够掌握总统府的的上网记录。为了到达这个目的，他们需要使所有从1号服务器到N号服务器的数据都经过至少一条他们所掌握的线路。

为了把这个计划付诸于行动，他们需要从这些线路的拥有者手中购买线路，每条线路都有对应的花费。自从公司的主要业务部是间谍活动而是家用宽带以后，经理就希望尽可能少的花费和尽可能高的回报。因此我们要使购买线路的平均值最小。

如果我们购买了k条线路，花费了c元，我们希望找到使c/k最小的方案。

【输入格式】

多组数据，每组数据第一行是两个整数n和m（1<=n<=100,1<=m<=400),代表服务器的个数和线路数

之后的m行，每行三个整数a，b，c，分别代表了这条线路所连接的服务器和购买这条线路的花费，花费都是正数且不会超过10^7

没有自边，没有重边，保证任意两点都是连通的。

最后一行为两个0

【输出格式】

每组数据的第一行是一个整数k，代表购买多少条线路

之后k个整数，代表购买线路的编号，编号是它们在输入文件被给处的顺序

每组数据之间有一个空行

【样例输入】

6 8
1 2 3
1 3 2
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3
4 5
1 2 2
1 3 2
2 3 1
2 4 2
3 4 2
0 0

【样例输出】

4 
3 4 5 6

3
1 2 3

【提示】

在此键入。

【来源】

在此键入。