问题 1386 --公路建设

1386: 公路建设

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版]

题目描述

2. 公路建设(road.pas)

 

【问题描述】

A国有N个城市,按123…,N编号。政府想大搞公路建设,提供了优惠政策:对于每一个投资方案的预计总费用,政府负担50%,并允许投资的公司对过往的汽车收取连续5年的养路费。世界各地的大公司纷纷投资,并提出了自己的建设方案,方案内容包括:公路连接的两座城市的编号,预计的总费用(假设他们的预计总是准确的)。

作为A国公路规划局的总工程师,有权利决定每一个方案是否接受,但是政府的要求是:

(1)       要保证各个城市之间都有公路直接或者间接相连

(2)       政府负担最少的费用

(3)       因为大公司并不是同时提出方案,政府希望每接到一个方案,就可以知道当前需要负担的最小费用和接受的投资方案,以便随时开工。关于你给投资公司的回复可以等到开工以后再给。

A国一开始是没有公路的。

【输入格式】

  第一行两个数字NMN<=500M<=2000

  第二行到第M+1行给出各个投资方案,第i行的编号为i-1,编号小的方案先接到,一个方案占一行,每行有3个数字,分别是连接的两个城市编号ab和投资的预计费用cost。(cost<=3000

【输出格式】

 输出文件共有M行,每一行的第一个数字是当前政府要负担的最少费用(保留1位小数),后面是X个数字,表示当前政府接受的方案的编号,不要求从大到小输出。但如果当前接受的所有方案不能保证政府的第一条要求,那么这一行只有一个数字0

注:红色文字部分暂时不输出!

【输入样例】

3 5

1 2 4

1 3 4

2 3 4

1 3 2

1 2 2

【输出样例】

0

4.0 1 2

4.0 1 2

3.0 1 4

2.0 4 5

输入

输出

提示


HJF:







题目要求对一个最小生成树做动态维护。处理的方法是:读入一条ab的边后,先不将这一条边加入图中,检查ab之间是否有路径相连,



1若相连则找到路径上权值最大的一条边e(u,v)



(1)e(u,v)的权值比新读入的这条边的权值要小或相等,则去掉新读入的边



(2)e(u,v)的权值比新读入的这条边的权值要大,则去掉e(u,v),加入新读入的边



2若不相连,则将新读入的边加入,这样,每次读入一条边后,仍能保持为最小生成树





来源

 


题目智能推荐


[提交][状态]