昼颜11,姐妹网,惊天危机 下载
目录
跑一边$\text{prim}$,然后找到最大值,如果有这等于$inf$输出-1
#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]; } } } } 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("-1\n"); return 0; }else ans=max_(ans,dis[i]); } cout<<ans; return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论