首页 > 代码库 > YYH的营救计划(NOIP模拟赛Round 6)
YYH的营救计划(NOIP模拟赛Round 6)
原题传送门
这道题目有2种做法:
1.kruskal
2.二分
对于第一种算法,我们知道最小的路一定在最小生成树上。这道题的原理可同NOIP货车运输
对于第二种算法,我们发现这道题的答案具有结论单调性,所以我们可以二分答案,然后用链表处理即可、。
下面贴第一种算法的代码
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m,s,t; struct edge{ int x,y,k; }bian[400001]; int f[200001]; bool cmp(edge a,edge b){return a.k<b.k;} int getfa(int x){return x==f[x]?x:f[x]=getfa(f[x]);} int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) scanf("%d%d%d",&bian[i].x,&bian[i].y,&bian[i].k); sort(bian+1,bian+m+1,cmp); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { int x=getfa(f[bian[i].x]),y=getfa(f[bian[i].y]); if(x!=y)f[x]=y; if(getfa(f[s])==getfa(f[t])) { printf("%d\n",bian[i].k); break; } } return 0; }
YYH的营救计划(NOIP模拟赛Round 6)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。