TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2747
  • Problem
  • P2747最小生成树1
    Limits : Time Limit : 15000 MS   Memory Limit : 234567 KB
    Description

    给定一个N个节点M条边的带权无向图,节点从1到N开始编号,求最小生成树

    Input Format

    第一行两个数N,M,表示点数和边数
    接下来M行每行三个数u,v,w,表示u,v之间有一条权为w的边
    可能有重边,但是没有自环

    Output Format

    如果最小生成树存在,输出树上所有边的权值和
    如果不存在,输出“Keng Die!”

    Sample Input

    4 5
    1 2 1
    2 3 2
    3 4 3
    4 1 4
    1 3 5

    Sample Output

    6

    Hint

    1<=N<=200000
    N-1<=M<=500000
    0<=每条边的权值<=5000


    Source  感谢nodgd放了一道水题