洛谷P1111 修复公路

作者: qwq 分类: ACM 发布时间: 2017-10-23 14:45

题目背景

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

题目描述

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

输入输出格式

输入格式:

第1行两个正整数N,M

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

输出格式:

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

输入输出样例

输入样例#1: 复制

4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出样例#1: 复制

5

说明

N<=1000,M<=100000

x<=N,y<=N,t<=100000

很简单的并查集。

解题方法是先按照时间来排序,从先到后。

每修好一个公路,检查一下是否全部完工。

用一个VIS数组来保存已经修好的村庄的数组。

当vis==n而且并查集只有一个集合的时候的时间,就是最小的t

 

#include<iostream>
#include<algorithm>
using namespace std;
int vis[1007];
int father[1007];
int n, m;
struct node {
	int start;
	int end;
	int time;

};
int  cmp(node a, node b) {
	return a.time < b.time;
}
int find(int a) {
	int x = a;
	while(father[x] != x) {
		x = father[x];
	}
	int y = a;
	int z;
	while(father[y] != y) {
		z = y;
		y = father[y];
		father[z] = x;

	}

	return x;

}
int ac() {
	int tot = 0;
	for (int i = 1; i <= n; ++i) {
		if(father[i] == i)
			tot++;
	}
	return tot;
}

void unionx(int a, int b) {
	int fa = find(a);
	int fb = find(b);
	father[fb] = fa;
}

int main() {

	cin >> n >> m;
	node a[100007];
	for (int i = 0; i < 1007; ++i) {
		father[i] = i;
	}
	for (int i = 0; i < m; ++i) {
		cin >> a[i].start >> a[i].end >> a[i].time;
	}
	int complish = 0;

	sort(a, a + m, cmp);
	int flag = -1;
	for (int i = 0; i < m; ++i) {

		unionx(a[i].start, a[i].end);

		if(vis[a[i].start] == 0) {
			complish++;
			vis[a[i].start] = 1;
		}
		if(vis[a[i].end] == 0) {
			complish++;
			vis[a[i].end] = 1;
		}
		if(complish >= n && flag == -1 && ac() == 1) {
			flag = a[i].time;
		}

	}

	cout << flag << endl;



}

 

 

一条评论
  • ERROR:

    2017年12月22日 下午11:13

    抱大腿…以后有问题请教你!可以留个QQ吗?

ERROR:进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注