文章目录
板子题题目解析算法解析代码
板子题
题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。 输入格式 第一行包含两个整数
N
,
M
N,M
N,M表示该图共有
N
N
N个结点和
M
M
M条无向边。 接下来
M
M
M行每行包含三个整数
X
i
,
Y
i
,
Z
i
X_i,Y_i,Z_i
Xi,Yi,Zi ，表示有一条长度为
Z
i
Z_i
Zi的无向边连接结点
X
i
,
Y
i
X_i,Y_i
Xi,YiX。 输出格式 如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz。
题目解析
首先，我们需要知道最小生成树是什么。 我们知道数是一个没有环的连通图，要在一张图里面找出边权和最小的一棵树就是最小生成树。
算法解析
这里我们以kruskal为例来讲解算法。 kruskal首先将每条边按照边权从小到大进行排序，这里通常使用快速排序，就是C++的sort。 然后从小到大来逐个判断这条边是否在同一个连通图内（假设这个图只有我们我们要加上的边），如果不是，就加上这条边。 当然，我们还要使用并查集来维护多个点是否在同一个连通图以内。
代码
#include<cstdio>
#include<algorithm>
#define maxn 200039
using namespace std
;
struct edge
{
int f
,t
,w
;
bool operator < (const edge x
) const {
return this->w
< x
.w
;
}
}a
[maxn
];
int f
[5039];
int getfa(int x
){
if(x
==f
[x
]) return x
;
f
[x
]=getfa(f
[x
]);
return f
[x
];
}
int n
,m
,i
,j
,k
;
int main(){
scanf("%d%d",&n
,&m
);
for(i
=0;i
<=n
;i
++)
f
[i
]=i
;
for(i
=1;i
<=m
;i
++)
scanf("%d%d%d",&a
[i
].f
,&a
[i
].t
,&a
[i
].w
);
sort(a
+1,a
+m
+1);
int k
=0;
int ans
=0;
for(i
=1;i
<=m
;i
++){
if(k
==n
-1){
printf("%d",ans
);
return 0;
}
if(getfa(a
[i
].f
)!=getfa(a
[i
].t
)){
f
[getfa(a
[i
].f
)]=a
[i
].t
;
k
++;
ans
+=a
[i
].w
;
}
}
printf("orz");
return 0;
}
发现自己变sb了连并查集都快不会打了
