洛谷 P1111 修复公路

题目链接

https://www.luogu.org/problemnew/show/P1111

以后只发题目链接！！！

题目大意

给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

解题思路

很显然，求的是一个最小瓶颈生成树。我的另一篇博客：https://www.cnblogs.com/yinyuqin/p/10779387.html#index_6

所以，我们只需要跑一边最小生成树。这里用的是Kruskal算法。

我们要求的是最早的时间，所以我们只需用t存时间即可。题目中还说如果不连通输出-1，只需统计边数，是否=n-1即可。

建议大家看一看另外一道题，一个思路但解释得更详细：https://www.cnblogs.com/yinyuqin/p/10786887.html

还有一个很重要的一点：输入规模很大，用cin会爆掉！！！

十年oi一场空，一个cin见祖宗。

最后附上正解：

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 using namespace std;

 struct edge{

     int qidian;

     int zhongdian;

     int value;

 }bian[];

 int n,m,fa[],t,cnt;

 bool cmp(edge a,edge b){

     return a.value<b.value;

 }

 int find(int x){

     if(fa[x]==x)return x;

     return fa[x]=find(fa[x]);

 }

 int main()

 {

 cin>>n>>m;

 for(int i=;i<=n;i++) fa[i]=i;

 for(int i=;i<=m;i++){

     scanf("%d%d%d",&bian[i].qidian,&bian[i].zhongdian,&bian[i].value);

 }

 sort(bian+,bian+m+,cmp);

 for(int i=;i<=m;i++){

     int p1=bian[i].qidian,p2=bian[i].zhongdian;

     int f1=find(p1),f2=find(p2);

     if(f1!=f2){

         cnt++;                //统计已加入最小生成树的边数

         t=bian[i].value;    //t为时间(因为value是递增的，所以不同取max了)

         fa[f1]=f2;

     }

 }

 if(cnt!=n-) cout<<-;

 else cout<<t;

 return ;

 }

AC代码

秒客网