c/c++语言开发共享洛谷 P3366 【模板】最小生成树

题目

戳

思路

最小生成树
$text{prim}$和$text{kruskal}$

$code$

$text{prim}$

/* prim+链式前向星 */ #include<bits/stdc++.h> #define maxn 5001 #define inf 1061109567 using namespace std; int n,m,cnt,ans; int dis[maxn],head[maxn]; bool vis[maxn]; struct edge{     int next,to,w; }edge[200001<<1]; inline int read(){     int x=0;bool f=0;char c=getchar();     while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}     return f?-x:x; } inline void addedge(int from,int to,int w){     edge[++cnt].to=to,edge[cnt].next=head[from];     edge[cnt].w=w,head[from]=cnt; } void prim(){     int tot=0,k=1;     dis[1]=0;     for(int i=head[1];i;i=edge[i].next){         if(dis[edge[i].to]>edge[i].w)             dis[edge[i].to]=edge[i].w;     }     while(++tot<n){         int sum=0x7fffffff;         vis[k]=1;         for(int i=1;i<=n;++i){             if(!vis[i]&&dis[i]<sum){                 k=i;                 sum=dis[i];             }         }         ans+=sum;         for(int i=head[k];i;i=edge[i].next){             if(!vis[edge[i].to]&&dis[edge[i].to]>edge[i].w)                 dis[edge[i].to]=edge[i].w;         }     } }  int main(){     memset(dis,0x3f3f3f,sizeof(dis));     n=read(),m=read();     int u,v,w;     while(m--){         u=read(),v=read(),w=read();         addedge(u,v,w),addedge(v,u,w);     }     prim();     for(int i=1;i<=n;++i){         if(dis[i]==inf){             printf("orzn");             return 0;         }     }     printf("%dn",ans);     return 0; }

/* prim+邻接矩阵 */ #include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #define maxn 5001 #define inf 1061109567 using namespace std; int n,m,ans; int map[maxn][maxn],dis[maxn]; bool vis[maxn]; inline int read(){     int x=0;bool f=0;char c=getchar();     while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}     return f?-x:x; } void prim(){     dis[1]=0;     for(int i=1;i<=n;++i){         int k=0;         for(int j=1;j<=n;++j){             if(!vis[j]&&dis[k]>dis[j]) k=j;         }         vis[k]=1;         for(int j=1;j<=n;++j){             if(!vis[j]&&map[k][j]<dis[j])                 dis[j]=map[k][j];         }     } }  int main(){     memset(map,0x3f3f3f,sizeof(map));     memset(dis,0x3f3f3f,sizeof(dis));     n=read(),m=read();     int u,v,w;     for(int i=1;i<=m;++i){         u=read(),v=read(),w=read();         if(map[u][v]>w){             map[u][v]=w;             map[v][u]=w;         }     }     prim();     for(int i=1;i<=n;++i){         ans+=dis[i];         if(dis[i]==inf){             printf("orzn");             return 0;         }     }     printf("%dn",ans);     return 0; }