TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1457
  • Problem
  • P1457坏电工
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

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

    Input Format

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

    Output Format

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

    Sample Input

    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

    Sample Output

    42

    Hint

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

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


    Source  改编自 USACO 2004 December Silver