目录
- code
题目
戳
思路
利用prim求该图的最小生成树,然后找到当中最大的那个数值输出,具体看代码吧,qwq。
code
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define max_(a,b) a>b?a:b; using namespace std; const int inf=1061109567; int n,m; bool vis[5001]; int map[5001][5001],dis[5001]; 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(){ for(int i=1;i<=n;++i){ int k=0; for(int j=1;j<=n;++j){ if(!vis[j]&&dis[j]<dis[k]) 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]; } } } }//prim int main(){ memset(map,0x3f3f3f,sizeof(map)); memset(dis,0x3f3f3f,sizeof(dis)); dis[1]=0; n=read(),m=read(); int x,y,w; for(int i=1;i<=m;++i){ x=read(),y=read(),w=read(); if(w<map[x][y]) map[x][y]=w,map[y][x]=w; } prim(); int ans=0; for(int i=1;i<=n;++i){ if(dis[i]==inf){//证明该图不连通 printf("-1n"); return 0; }else ans=max_(ans,dis[i]); } cout<<ans; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602945.html