简单的prim算法，虽然我现在刚学
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=500+10; int mapp[maxn][maxn]; int n; const int inf=0x3f3f3f3f; void prim() { int maxlen=-1; bool vis[maxn]; int mincost[maxn]; memset(vis,false,sizeof(vis)); for(int i=1; i<=n; i++) mincost[i]=mapp[1][i]; vis[1]=true; int v; for(int j=2; j<=n; j++) { int mini=inf;//每次更新一遍最小值，作为寻找标准 for(int i=1; i<=n; i++) if(!vis[i]&&mincost[i]<mini)//寻找最小的下一个节点 { v=i; mini=mincost[i]; } vis[v]=true; if(mini!=inf&&mini>maxlen) maxlen=mini; for(int i=1; i<=n; i++) if(!vis[i]) mincost[i]=min(mincost[i],mapp[v][i]);//更新，寻找此节点到下一个节点的最小值 } printf("%d\n",maxlen); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { int m; scanf("%d",&m); mapp[i][j]=mapp[j][i]=m;//存储 } prim(); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/6616450.html
