洛谷 P1111 修复公路

矫情吗；* 2023-07-13 03:27 1阅读 0赞

## 题目背景 ##

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

## 题目描述 ##

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

## 输入格式 ##

第111行两个正整数N,MN,MN,M

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

## 输出格式 ##

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

## 输入输出样例 ##

**输入 \#1**

4 4
    1 2 6
    1 3 4
    1 4 5
    4 2 3

**输出 \#1**

## 说明/提示 ##

N≤1000,M≤100000N \\le 1000,M \\le 100000N≤1000,M≤100000

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

**思路：使用kruskal算法，在算法进行过程中记录最大边权（最大时间）。**

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<deque> 
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 1000002; 
    const int INF = 10000000;
    
    struct Edge{
    	int u,v,t;
    	Edge(int u,int v,int t){
    		this->u = u;
    		this->v = v;
    		this->t = t;
    	}
    };
    vector<Edge> edges;
    int father[MAXN];
    
    void initFather(int n){
    	for(int i=0;i<=n;i++){
    		father[i] = i;
    	}	
    }
    
    int findFather(int x){
    	int z = x;
    	while(x != father[x]){
    		x = father[x];
    	}
    	int a;
    	while(z != father[z]){
    		a = z;
    		z = father[z];
    		father[a] = x;
    	}
    } 
    
    bool unionFather(int x,int y){
    	int fx = findFather(x);
    	int fy = findFather(y);
    	if(fx != fy){
    		father[fy] = fx;
    		return false; //不是同一个祖宗，可以加入 
    	}
    	return true; //是同一个祖宗，不可以加入 
    }
    
    bool cmp(const Edge &edge1,const Edge &edge2){
    	return edge1.t < edge2.t;
    }
    
    int kruskal(int n){
    	int minTime = -1;
    	initFather(n);
    	sort(edges.begin(),edges.end(),cmp);
    	int cnt = 0;
    	for(int i=0;i<edges.size();i++){
    		Edge edge = edges[i];
    		int u = edge.u;
    		int v = edge.v;
    		int t = edge.t;
    		if(!unionFather(u,v)){
                            //记录最大边权
    			minTime = max(minTime,t);
    			cnt++;
    			if(cnt == n-1){
    				break;
    			}
    		}
    	}
    	if(cnt < n-1){
    		minTime = -1;
    	} 
    	return minTime;
    }
    
    int main(){
    	int n,m;
    	int u,v,t;
    	cin>>n>>m;
    	while(m--){
    		cin>>u>>v>>t;
    		edges.push_back(Edge(u,v,t));
    	}
    	cout<<kruskal(n)<<endl;
    	return 0; 
    }