最小生成树知识点 2022-10-07 436- 2m- - 学力扣-最小生成树prim prim算法 int k(int n,int m){if(m>n) swap(n,m);return m==1?n:k(m,n%m);} int prim(){ memset(dist,0x3f,sizeof dist); int res=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1 || dist[t] > dist[j] )) t=j; st[t]=true; if(i) res+=dist[t]; if(i&&dist[t]==INF) return INF; for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); } return res;} #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N=2022;const int INF=0x3f3f3f3f;int g[N][N],dist[N];bool st[N];//是否访问过int n,m;int prim(){ memset(dist,0x3f,sizeof dist); int res=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++)//在所有节点中 if(!st[j]&&(t==-1 || dist[t] > dist[j] )) t=j;//第一个节点或者距离更小,更新节点选择 st[t]=true;//设置该节点为已访问 if(i) res+=dist[t];//如果不是第一个,结果加上该节点距离 if(i&&dist[t]==INF) return INF;//如果所有边的最短边是INF,一定是INF for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);//更新所有节点距集合距离为加上新节点的距离 } return res;}int main(void){ cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) g[i][j]=0; else g[i][j]=INF; } } for(int i=1;i<=2021;i++) { for(int j=1;j<=2021;j++) { if(i!=j) { int a=i,b=j; int sum=0; while(a||b) { if(a%10!=b%10) sum+=a%10+b%10; a/=10,b/=10; } g[i][j]=sum; g[j][i]=sum; } } }//邻接矩阵建边 int t=prim(); cout<<t<<endl; return 0;} 我很可爱,请给我钱本文作者:shedding-ash本文链接:https://www.shedding-ash.top/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/版权声明:本博客所有文章除特别声明外,均默认采用 许可协议。