本文共 849 字,大约阅读时间需要 2 分钟。
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出orz
输入输出格式
输入格式: 第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000) 接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi
输出格式:
输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz
输入输出样例
输入样例#1: 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 输出样例#1: 7
这段代码其实出现了一点小错误,但我实在不知道错在哪。。。
#include#include #include using namespace std;//最小生成树之kruskal 也就是使用并查集//第一个是判断 边是否在同一个子集之中 第二个就是判断 边之间的合并int a[100]={ 0};////再创建一个结构体数组来存储 起点,终点 和边的长度struct jj{ int x,y,z;}J[100];//写一个判断祖宗的方法int zuzong(int x){ if(a[x]==x) return x; else return zuzong(a[x]);}//写一个判断的方法bool check(int x,int y){ return zuzong(x)==zuzong(y);}//再写一个合并的方法void merge_1(int x,int y){ if(!check(x,y)) a[zuzong(x)]=zuzong(y);}//再写一个比较的方法,用边的长度作为比较对象bool cmp(jj x,jj y){ //名字要取好 return x.z
转载地址:http://ekfen.baihongyu.com/