我的第一篇博客吧，看到周围人的博客，的确挺佩服那些dalao,同时意识到博客确实是个学习的好东西，在纠结过博客园和csdn后，选择了简书，哈哈哈，有点想笑，有点zz的感觉，还是看看刚学的克鲁斯卡尔吧，先看题目。
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz
输入输出格式
输入格式：
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）
接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi
输出格式：
输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz
输入输出样例
输入样例#1： 复制
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
**输出样例#1 **复制：
7
说明
时空限制：1000ms,128M
数据规模：
对于20%的数据：N<=5，M<=20
对于40%的数据：N<=50，M<=2500
对于70%的数据：N<=500，M<=10000
对于100%的数据：N<=5000，M<=200000
自己的理解：
克鲁斯卡尔基本上就是并查集加贪心（个人理解）。结构体存边，这样便于排序，毕竟每条边的全职和连接点需要一一对应；之后把所有的边排序，鉴于本人较懒，直接sort了；然后就是枚举从小到大开始枚举所有边，因为是最小生成树，所加的边肯定是从小的边开始；这就是我们的一个贪心思想；需要在枚举时判断连个点是否在最小生成树中，如果不在就sum就加上该边权值（sum表示最小生成树的权值和），然后有用并查集把他们放进一个集合；如果在最小生成树中，即已经标记过，直接跳过。连接n个点需要的边必定是n-1条（不信的话可以自己画一下）；所以当所有的进入最小生成树中的边数为n-1时可以直接跳出，最小生成树已经找出；
要点步骤：
1.结构体存边；
2.对所有的边进行排序；
3.从小到大枚举所有边；
4.将可以的边（即还未在最小生成树中的点）通过并查集合并，同时计算权值和；
5.如果已经有n-1条边则最小生成树已经找出；
（我犯了一个错误就是没有考虑orz的情况,不过luogu的题解也有很多没有考虑这种情况，可见数据还可以加强，，，）
经学长点拨，只需要在外面判断一下，所加边数不等于n-1即最小生成树未生成，也就说明，有未联通的点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read(){//读入优化
int x = 0;int f = 1;char c = getchar();
while(c<'0' || c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct edge{//结构体存边
int u;int v;int w;
};
struct edge e[200005];
int f[500521];
int sum;
int ans;
int n;int m;
bool cmp(edge x,edge y){
return x.w<y.w;
}
int query(int v){//并查集查询
if(f[v] == v)return v;
else return f[v] = query(f[v]);//路径压缩
}
int merge(int v,int u){//并查集合并
int t1 = query(v);
int t2 = query(u);
if(t1 != t2){
if(rand()%2)f[t1] = t2;//zhx教的防止并查集被卡的小妙招
else f[t2] = t1;
return 1;
}
return 0;
}
int main(){
n = read();m = read();
for(int i = 1;i <= m;i++){
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
sort(e+1,e+m+1,cmp);//从小到大排序 以e[I].w为关键字进行排序
for(int i = 1;i <= n; i++)f[i] = i;
//kruskal
for(int i = 1;i <= m; i++){//枚举所有边
if(merge(e[i].u,e[i].v)){//如果双方有一个或者都未进最小生成树
ans++;sum += e[i].w; //ans表示已经找出最小生成树中多少边
// 并求出权值和
}
if(ans == n-1)break;//找出一个最小生成树
}
printf("%d",sum);
return 0;
}
考虑图未联通的情况的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read(){
int x = 0;int f = 1;char c = getchar();
while(c<'0' || c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct edge{
int u;int v;int w;
};
struct edge e[200005];
int f[500521];
int sum;
int ans;
int n;int m;
bool cmp(edge x,edge y){
return x.w<y.w;
}
int query(int v){
if(f[v] == v)return v;
else return f[v] = query(f[v]);
}
int merge(int v,int u){
int t1 = query(v);
int t2 = query(u);
if(t1 != t2){
if(rand()%2)f[t1] = t2;
else f[t2] = t1;
return 1;
}
return 0;
}
int main(){
n = read();m = read();
for(int i = 1;i <= m;i++){
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
sort(e+1,e+m+1,cmp);
for(int i = 1;i <= n; i++)f[i] = i;
//kruskal
for(int i = 1;i <= m; i++){
if(merge(e[i].u,e[i].v)){
ans++;sum += e[i].w;
}
if(ans == n-1)break;
}
if(ans != n-1){//判断一下是否生成最小生成树如果生成直接输出
printf("orz");
return 0;//程序结束
}
printf("%d",sum);
return 0;
}
