提示:Prim 算法请开 O2 优化。
给出一个无向图,求出最小生成树
第一行包含两个整数 N,MN,MN,M,表示该图共有 NNN 个结点和 MMM 条无向边。
接下来 MMM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_iXi,Yi,Zi,表示有一条长度为 ZiZ_iZi 的无向边连接结点 Xi,YiX_i,Y_iXi,Yi。
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
7
1≤N≤5×1051\le N\le 5\times 10^51≤N≤5×105
1≤M≤5×1051\le M\le 5\times 10^51≤M≤5×105
1≤Xi,Yi≤N1 \le X_i,Y_i \le N1≤Xi,Yi≤N
1≤Zi≤1041\le Z_i \le 10^41≤Zi≤104
Xi≠YiX_i ≠ Y_iXi=Yi
在以下作业中:
并查集
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 CZOJ 通用账户