洛谷 P3366 【模板】最小生成树
程序员文章站
2022-06-14 17:28:48
[TOC] 题目 "戳" 思路 最小生成树 "$\text{Prim}$和$\text{Kruskal}$" $Code$ $\text{Prim}$ cpp / Prim+链式前向星 / include define MAXN 5001 define inf 1061109567 using na ......
目录
题目
思路
最小生成树
$\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("orz\n"); return 0; } } printf("%d\n",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("orz\n"); return 0; } } printf("%d\n",ans); return 0; }