洛谷 P1111 修复公路

[TOC]

###题目 P1111 修复公路 ###思路 方法一：跑一遍最小生成树（$ ext(或) ext(，我用的) ext$）,然后找到最大值，如果有等于$inf$就输出-1 方法二：并查集，先按照耗费时间由小到大排序，一开始联通块数量为$n$每连接两个不相同的联通块联通块数量减一，当联通块数量减到一时输出当前这条路的耗费的时间 ###(Code) 方法一：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define max_(a,b) a>b?a:b;
using namespace std;
const int inf=1061109567;
int n,m;
bool vis[5001];
int map[5001][5001],dis[5001];
inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}
void Prim(){
	for(int i=1;i<=n;++i){
		int k=0;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&dis[j]<dis[k]) k=j;
		}
		vis[k]=1;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&map[k][j]<dis[j]){
				dis[j]=map[k][j];
			}
		}
	}
}

int main(){
	memset(map,0x3f3f3f,sizeof(map));
	memset(dis,0x3f3f3f,sizeof(dis));
	dis[1]=0;
	n=read(),m=read();
	int x,y,w;
	for(int i=1;i<=m;++i){
		x=read(),y=read(),w=read();
		if(w<map[x][y]){
			map[x][y]=w,map[y][x]=w;
		}
	}
	Prim();
	int ans=0;
	for(int i=1;i<=n;++i){
		if(dis[i]==inf){
			printf("-1
");
			return 0;
		}else ans=max_(ans,dis[i]);
	}
	cout<<ans;
	return 0;
}

方法二：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n,m,fa[1001],r[1001];
struct info{
	int u,v,c;
}a[MAXN];
bool cmp(info a,info b){
	return a.c<b.c;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
	int rootx=find(x),rooty=find(y);
	if(rootx==rooty) return;
	if(r[rootx]>r[rooty]) fa[rooty]=rootx;
	else if(r[rooty]>r[rootx]) fa[rootx]=rooty;
	else{
		fa[rootx]=rooty;
		r[rooty]++;
	}
}
inline int read(){
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1,x,y,w;i<=m;++i) a[i].u=read(),a[i].v=read(),a[i].c=read();
	sort(a+1,a+m+1,cmp);
	int ub=n;
	for(int i=1;i<=m;++i){
		if(find(a[i].u)!=find(a[i].v)){
			Union(a[i].u,a[i].v);
			ub--;
		}
		if(ub==1){
			printf("%d
",a[i].c);
			return 0;
		}
	}
	puts("-1");
	return 0;
}