这个是图论的倒数第二章。我会着重讲解最小生成树和拓扑排序两个算法。如果哪些地方我写错的,或者没写清楚的,可以评论区吐槽~
先看一道洛谷上面的题目。
题目大意就是给n个点,m对长度,求一个最小生成树。
什么叫做最小生成树?我们之前讲树的时候提到过,树一共有n-1条边,然后每条边都是一个割边—删去这条边,图就不连通。最小生成树就像上题所说,找出一部分边,保证整个图是联通的,并且所有边的长度最小。
我们再仔细思考一下,要保证边的总长度最小,是不是必须要是一棵树?可以说是的,如果这一张图,某条边不是割边(删除后依旧是连通图),那么我们删去他,也能满足条件,并且边的长度更小。(这里的前提是所有边的权值是正数)同时,如果所有的边都是割边,那显然这应该是一棵树。
好的。我们该如何找到这棵树?
很明显,我们能想到一个贪心的算法。实际上我们的目标就是找到n-1条长度最小的边,然后要保证这些边能使得所有点连通。
我们来试一试。下面有一张图。
这个算法叫Kruskal算法。时间复杂度O(ElgV)
我重新描述一下整个算法过程。
1. 先将所有的边按照长度从小到8大排序。
2. 从小到大遍历。如果这条边没必要连接(连接会导致成环),就舍弃这条边;否则我们就将这条边连起来。
3. 最后形成的图就是最小生成树。
并查集可以让我们知道两个区块是否联通,我们只要判断这条边连接的两个点是否是联通的就行(即根节点是否相同)
洛谷标程如下:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll fa[100005];
struct node{
ll x,y,c;
}a[100005]; //代表每条边连接x和y长度为c
ll n,m;
ll find_fa(ll x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;} //并查集核心算法
bool cmp(node x,node y){return x.c<y.c;} //边排序
ll read(){ //快读
char c=getchar();ll x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x;
}
int main(){
n=read();m=read();
ll ans=0;
for(ll i=1;i<=m;i++){a[i].x=read();a[i].y=read();a[i].c=read();}
for(ll i=0;i<n;i++) fa[i]=i;
sort(a+1,a+1+m,cmp);
for(ll i=1;i<=m;i++){
ll fx=find_fa(a[i].x),fy=find_fa(a[i].y);
if(fx!=fy){
ans+=a[i].c;
fa[fx]=fy;
}
}
cout<<ans<<endl;
return 0;
}
存稿用完啦!大家有问题可以留言~