【模板】最小生成树 [最小生成树][prim kruskal]

prim

先建立一个只有一个结点的树，这个结点可以是原图中任意的一个结点

使用一条边扩展这个树，要求这条边一个顶点在树中另一个顶点不在树中，并且这条边的权值要求最小。

重复步骤2直到所有顶点都在树中

又双叒叕看学长的模板写的顺便重新感性理解优先队列

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=1000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
int n,m;
ll ans=0;
typedef pair<int,int>pii;                        //pair
priority_queue<pii,vector<pii>,greater<pii> >q; //小顶堆 
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int tot=0,head[N];
struct edge{int v,nxt,w;}e[M<<1];
void add(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w};head[u]=tot;
}

int dis[N],vis[N];
void prim(){
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    q.push(make_pair(dis[1]=0,1));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        ans+=dis[u],vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(!vis[v]&&dis[v]>w){
                dis[v]=w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    rd(n),rd(m);
    int u,v,w;
    for(rg int i=1;i<=m;++i){
        rd(u),rd(v),rd(w);
        add(u,v,w),add(v,u,w);
    }
    prim();
    printf("%lld",ans);
    return 0;
}

P3366 【模板】最小生成树加一个cnt来记录加了多少个点最后不足n个则表明没有连通

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<stack>
 7 #include<algorithm>
 8 using namespace std;
 9 #define ll long long
10 #define rg register
11 const int N=5000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
12 int n,m;
13 ll ans=0;
14 typedef pair<int,int>pii;                        //pair
15 priority_queue<pii,vector<pii>,greater<pii> >q; //小顶堆 
16 template <class t>void rd(t &x){
17     x=0;int w=0;char ch=0;
18     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
19     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
20     x=w?-x:x;
21 }
22 
23 int tot=0,head[N];
24 struct edge{int v,nxt,w;}e[M<<1];
25 void add(int u,int v,int w){
26     e[++tot]=(edge){v,head[u],w};head[u]=tot;
27 }
28 
29 int dis[N],vis[N],cnt=0;
30 bool prim(){
31     memset(vis,0,sizeof(vis));
32     memset(dis,inf,sizeof(dis));
33     q.push(make_pair(dis[1]=0,1));
34     while(!q.empty()){
35         int u=q.top().second;q.pop();
36         if(vis[u]) continue;
37         ans+=dis[u],vis[u]=1,++cnt;
38         for(int i=head[u];i;i=e[i].nxt){
39             int v=e[i].v,w=e[i].w;
40             if(!vis[v]&&dis[v]>w){
41                 dis[v]=w;
42                 q.push(make_pair(dis[v],v));
43             }
44         }
45     }
46     if(cnt!=n) return 0;
47     else return 1;
48 }
49 int main(){
50     rd(n),rd(m);
51     int u,v,w;
52     for(rg int i=1;i<=m;++i){
53         rd(u),rd(v),rd(w);
54         add(u,v,w),add(v,u,w);
55     }
56     if(!prim()) printf("orz");
57     else printf("%lld",ans);
58     return 0;
59 }
60

3366 prim

/*prim
*/
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1000001,M=1000001,inf=1e9;
int n,m,o,hd[N],dis[N],vis[N];
typedef pair<int,int>pii;                        //pair
priority_queue<pii,vector<pii>,greater<pii> >q; //小顶堆 
struct Edge{int v,nt,w;}E[M<<1];
int main()
{//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    o=1;
    for(int i=1;i<=n;i++)dis[i]=inf;
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        E[o]=(Edge){v,hd[u],w}; hd[u]=o++;
        E[o]=(Edge){u,hd[v],w}; hd[v]=o++;
    }
    q.push(make_pair(dis[1]=0,1));
    ll ans=0;
    while(!q.empty()){
        int u=q.top().second; q.pop();//记得pop! 
        if(vis[u])continue;
        vis[u]=1;
        ans+=dis[u];
        for(int i=hd[u];i;i=E[i].nt){
            int v=E[i].v;
            if(!vis[v]&&dis[v]>E[i].w){//和dijkstra不同！ 
                dis[v]=E[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}//by tkys_Austin;

学长's

kruskal

将边按照边权从小到大排序，并建立一个没有边的图T

选出一条没有被选过的边权最小的边。

如果这条边两个顶点在T中所在的连通块不相同，那么将它加入图T

重复2和3直到图T连通为止。

由于只需要维护连通性，可以不需要真正建立图T，可以用并查集来维护

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=1000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,cnt=0,f[N];
ll ans=0;

template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

struct edge{
    int u,v,w;
    bool operator<(const edge&A)const{return w<A.w;}
}e[M];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

void kruskal(){
    for(rg int i=1;i<=n;++i) f[i]=i;
    for(rg int i=1,u,v;i<=m;++i){
        u=e[i].u,v=e[i].v;
        if(find(u)!=find(v)){
            f[f[u]]=f[v];
            ans+=e[i].w;
        }
    }
}

int main(){
    rd(n),rd(m);
    for(int i=1,u,v,w;i<=m;++i){
        rd(u),rd(v),rd(w);
        e[i]=(edge){u,v,w};
    }
    sort(e+1,e+1+m);
    kruskal();
    printf("%lld",ans);
    return 0;
}

/*kruskal
*/ 
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000001,M=1000001;
int n,m,f[N],cnt; 
struct edge{
    int u,v,w;
    bool operator<(const edge&A)const{
        return w<A.w;
    }
}e[M];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main()
{    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    ll ans=0;
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        e[++cnt]=(edge){u,v,w};
    }
    sort(e+1,e+cnt+1);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,u,v;i<=m;i++){
        u=e[i].u; v=e[i].v;
        if(find(u)!=find(v)){
            f[f[u]]=f[v];
            ans+=e[i].w;
        }
    }
    cout<<ans<<endl;
    return 0;
}//by tkys_Austin;

学长's