预备役间学习记录9-创新互联

## 题目背景

$A$地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

## 题目描述

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

## 输入格式

第$1$行两个正整数$N,M$

下面$M$行，每行$3$个正整数$x, y, t$，告诉你这条公路连着$x,y$两个村庄，在时间t时能修复完成这条公路。

## 输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出$-1$，否则输出最早什么时候任意两个村庄能够通车。

## 样例 #1

### 样例输入 #1

```

4 4

1 2 6

1 3 4

1 4 5

4 2 3

```

### 样例输出 #1

```

5

```

## 提示

$N \le 1000,M \le 100000$

$x \le N,y \le N,t \le 100000$

1. 并查集，我们定义一个结构体数组来存村庄关系，和之间的时间，定义一个数组记录集合；

2. 按时间从小到大对结构体数组排序；

3. 之后，对结构体从i=1;i<=n;i++开始检索，并进行并查，到查到所有村庄都到一个集合时，此时检索到的关系时间就是最短时间，如果i>n还没到一个集合则输出-1

附代码

#include#include
using namespace std;

struct jh
{int x;
 int y;
 int t;
}zj[100000]; 

int jl[100000];

int bj(const jh &a,const jh &b){return a.t>n>>m;
 for(int i=0;i>zj[i].x>>zj[i].y>>zj[i].t;if(zj[i].x>maxx)maxx=zj[i].x;if(zj[i].y>maxx)maxx=zj[i].y;}
 
 sort(zj,zj+m,bj);
 
 if(n==1){cout<<0;k=2;}
 else
 for(int i=0;imaxt){maxt=zj[i].t;}
  
  if(jl[zj[i].x]==0&&jl[zj[i].y]==0)
  {jl[zj[i].x]=jl[zj[i].y]=i+1;}
  else
  if(jl[zj[i].x]!=0&&jl[zj[i].y]==0)
  {jl[zj[i].y]=jl[zj[i].x];}
  else
  if(jl[zj[i].x]==0&&jl[zj[i].y]!=0)
  {jl[zj[i].x]=jl[zj[i].y];}
  else
  {int z=jl[zj[i].x];
   int x=jl[zj[i].y];
   for(int i=0;i<=maxx;i++)
   if(jl[i]==z)jl[i]=x;
  }
  
  int j,js=1;
  for(j=2;j<=maxx;j++)
  {if(jl[j]!=jl[1]||jl[1]==0)break;else js++;}
  
  if(js==n&&jl[1]!=0){cout<

#include#include
using namespace std;

struct tree
{int z;
 int y;
}jl[1000010];

int max1,n;

void zhao(int jd,int cs)
{if(jl[jd].z==0&&jl[jd].y==0)
 {max1=max1>n;
 for(int i=1;i<=n;i++)
 {cin>>jl[i].z>>jl[i].y;}
 
 zhao(1,1);
 
 cout<