TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1457
  • 题目
  • P1457【NK月赛 May2012 T2】坏电工
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板买了一栋别墅。这栋别墅总共有N(2<=N<=1000)个房间,何老板把他们编号为1到N。何老板想给每个房间都牵上网线。他雇了一个电工来连网线。电工做了测量,这N个房间之间最多能连M条网线。每条网线都需要一定的花费C(1 <= C <= 100,000)。何老板想用最小的费用让所有房间都连上网络。

    何老板经常拖欠农民工工资。之前好几次工作的工资何老板都还没发给这个电工。于是这个电工想报复何老板。这个电工决定做下面事情:
    1.让何老板花的钱尽可能多。
    2.让每个房间都连上网络(让何老板感觉他很好地完成了工作)。
    3.让所有连线不构成环(如果有环会被何老板发现)
    问:电工最多让何老板花费多少?

    输入格式

    第一行,两个空格间隔的整数N和M
    接下来M行,每行三个空格间隔的整数A、B、C表示连接A和B两个房间的网线花费为C。

    输出格式

    一个整数,何老板需支付的最大费用,若无法用网线将所有房间连接起来,输出-1。

    样例输入

    5 8
    1 2 3
    1 3 7
    2 3 10
    2 4 4
    2 5 8
    3 4 6
    3 5 2
    4 5 17

    样例输出

    42

    提示

    最贵的连接方案会花费 17 + 8 + 10 + 7 = 42。
    连接方案如下:
    4连5
    2连5
    2连3
    1连3

    注意:两个房间之间有可能有多种不同价格的连线方式。


    来源  改编自 USACO 2004 December Silver