• [C] Bridge And Island

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • In order to strengthen the communication between the island, the government wants to build bridges between some islands. Now, the government gives you the cost money between each island, can you find the way to build bridges to link all islands but cost the minimum money.

  • 输入
  • Input until EOF.
    First line will give you two integers N (4 <= N <= 100)(the id of islands are from 1 to N) and M (N - 1 <= M <= N * (N - 1) / 2), N means the number of islands, M means the number of bridges can be built.
    Next M lines, each line contains three integers x, y, and c (0 < c < 100), means there exists the cost money c between x and y.
    For data.in, there will not exist two bridges between two islands, and all islands will be linked by bridges.
  • 输出
  • Print the minimum cost money to link all islands.
  • 样例输入
  • 4 6
    1 2 1
    1 3 1
    1 4 1
    2 3 2
    2 4 2
    3 4 2
    
  • 样例输出
  • 3
    
  • 提示
  • 来源
  • Hungar
  • 操作

显示春菜