Luogu P3366 【模板】最小生成树题解

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例#1：

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

最小生成树板子题，没什么好说的……

算法说明：

以下两个算法都基于贪心实现。

kruskal算法采用并查集思想。步骤如下：

把每个点单独拆分，使得每个点的父亲都是它自己，即每个点单独成一个连通块。
每次取最短边，如果边两端的点处于同一个连通块，则pop掉，再取最短的边，直到边两端的点不处于同一个连通块为止。
合并两个点所在的连通块，并且ans+=两个点的距离。
重复2和3，共n-1遍。

prim算法采用遍历。步骤如下：

初始把1号点标记为已经使用过，并将与其相连的所有边加入队列。
每次取最短边，如果边的终点已使用过，则pop掉，再取最短的边，直到边的终点未使用过为止，
将边的终点标记为已经使用过，并且ans+=该边长度，再将与该边终点相连的所有边加入队列。
重复2和3，共n-1遍。
*因为每次选择可用的新边时，该边起点都是已经使用过的（所以该边才有加入队列），所以只要判断该边终点即可。

代码：

kruskal算法：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct edge{
    int u,v,w;
};
int n,m,f[5010],v[5010];
priority_queue<edge,vector<edge>,greater<edge> >q;
bool operator >(const edge &a,const edge &b){
    return a.w>b.w;
}
int find(int x){
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
inline void join(int x,int y){
    f[x]=y;
}
long long kruskal()
{
    long long ans=0;
    for(int x=1;x<n;x++)
    {
        edge temp=q.top();
        while(find(temp.u)==find(temp.v))
        {
            q.pop();
            temp=q.top();
        }
        q.pop();
        int tu=find(temp.u),tv=find(temp.v);
        join(tu,tv);
        ans+=temp.w;
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    while(m--)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        v[x]=v[y]=1;
        edge temp;
        temp.u=x;
        temp.v=y;
        temp.w=z;
        q.push(temp);
    }
    for(int i=1;i<=n;i++)
        if(!v[i]){
            cout<<"orz";
            return 0;
        }
    cout<<kruskal();
    return 0;
}

prim算法：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct edge{
    int v,w;
};
int n,m;
bool v[5010]={false};
vector<edge>G[5010];
priority_queue<edge,vector<edge>,greater<edge> >q;
bool operator >(const edge &a,const edge &b){
    return a.w>b.w;
}
long long prim()
{
    long long ans=0;
    v[1]=1;
    for(vector<edge>::iterator i=G[1].begin();i!=G[1].end();i++)
        q.push(*i);
    int x=1;
    while(x++<n){
        edge temp=q.top();
        while(v[temp.v]){
            q.pop();
            temp=q.top();
        }
        ans+=temp.w;
        v[temp.v]=1;
        for(vector<edge>::iterator i=G[temp.v].begin();i!=G[temp.v].end();i++)
            q.push(*i);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        edge temp;
        temp.v=y;
        temp.w=z;
        G[x].push_back(temp);
        temp.v=x;
        G[y].push_back(temp);
    }
    for(int i=1;i<=n;i++){
        if(G[i].empty()){
            cout<<"orz";
            return 0;
        }
    }
    cout<<prim();
    return 0;
}