目录
- $code$
题目
戳
思路
最小生成树
$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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602666.html