图论——最小生成树(1)

最小生成树一般是求边权之和最小。Prim算法和Kruskal算法是求解最小生成树的两种算法。

//Prim算法堆优化
#include<iostream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 400500
using namespace std;
struct edge{
	int u,v,w;
}e[maxn];
struct node{
	int u,dis;
	bool operator <(const node&a)const{
		return dis>a.dis;
	}
};
int tot=0,h[maxn],nxt[maxn],n,m,x,y,z,cnt=0;
bool vis[maxn];
long long dis[maxn];
void add(int u,int v,int w){
	e[++tot]={u,v,w};
	nxt[tot]=h[u];
	h[u]=tot;
}
void prim(){
	for(int i=0;i<=n;++i){
		dis[i]=inf;
	}
	dis[1]=0;
	priority_queue<node> q;
	q.push({1,0});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u]) continue;
		cnt++;
		vis[u]=1;
		for(int i=h[u];i>0;i=nxt[i]){
			int v=e[i].v;
			int w=e[i].w;
			if(!vis[v]&&dis[v]>w){
				dis[v]=w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	prim();
	long long sum=0;
	for(int i=1;i<=n;++i){
		sum+=dis[i];
	}
	if(cnt==n) cout<<sum;
	else cout<<"orz";
}
//Prim算法朴素
void prim(){
    for(int i=0;i<=n;++i){
        dis[i]=1e9;
    }
    dis[1]=0;
    for(int i=1;i<=n;++i){
        int u=0;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&dis[j]<dis[u]){
                u=j;
            }
        }
        if(vis[u]) continue;
        vis[u]=1;
        for(int k=h[u];k>0;k=e[k].nxt){
            int v=e[k].v;
            int w=e[k].w;
            if(!vis[v]&&dis[v]>w){
                dis[v]=w;
            }
        }
    }
}
//Kruskal算法
#include<iostream>
#include<vector>
#include<algorithm> // Kruskal 需要 sort
#define inf 0x3f3f3f3f
#define maxn 400500
using namespace std;
struct edge{
	int u,v,w;
	bool operator <(const edge&a)const{
		return w<a.w;
	}
}e[maxn];
int fa[maxn];
int n,m,x,y,z,cnt=0;
long long sum=0;
int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void kruskal(){
	for(int i=1;i<=n;++i){
		fa[i]=i;
	}
	sort(e+1,e+m+1);
	for(int i=1;i<=m;++i){
		int u=e[i].u;
		int v=e[i].v;
		int w=e[i].w;
		int fu=find(u);
		int fv=find(v);
		if(fu!=fv){
			fa[fu]=fv; 
			sum+=w;    
			cnt++;     
			if(cnt==n-1) break; 
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		e[i]={x,y,z};
	}
	kruskal();
	if(cnt==n-1) cout<<sum;
	else cout<<"orz";
	return 0;
}