TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1457
  • 問題
  • P1457坏电工
    制限 : 時間制限 : 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。 M<=100000

    出力形式

    一个整数,何老板需支付的最大费用,若无法用网线将所有房间连接起来,输出-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