首页 > 代码库 > YYH的营救计划
YYH的营救计划
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int maxm=400100; struct edge{int f,t,c;}g[maxm]; bool cmp(edge x,edge y){return x.c<y.c;} int fa[maxm],n,m,s,t; int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void unite(int x,int y){ int fx=find(x),fy=find(y); if(fx==fy)return; fa[fx]=fy; } int kru(){ sort(g+1,g+m+1,cmp); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ edge x=g[i]; if(find(x.f)!=find(x.t)){ unite(x.f,x.t); if(find(s)==find(t))return g[i].c; } } } int main() { n=read();m=read();s=read();t=read(); for(int i=1;i<=m;i++){ int x,y,z; x=read();y=read();z=read(); g[i]=(edge){x,y,z}; } cout<<kru(); return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
YYH的营救计划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。