注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

石门实验中学卢凯宾的博客

向前跑,迎着冷眼和嘲笑。

 
 
 

日志

 
 

洛谷1111 -- 修复公路  

2015-12-27 14:22:24|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:有N个村庄和M条双向公路,给定每条公路连着的两个村庄和修完这条公路的时间。问最早什么时候任意两个村庄能够通车。
分析:通车的村庄在同一个集合里,本质上也是并查集。先按时间排序,修公路的顺序按时间从早到晚。每修一条公路就判断整个图是否连通。
代码:
# include <algorithm>
# include <cstdio>

const int SIZEN=1000+5;
const int SIZEM=100000+5;

struct Tnode {
	int x , y , t ;
} road[SIZEM];

int N , M , f[SIZEN] ;

bool _cmp ( Tnode , Tnode ) ;

int _find ( int ) ;
void _union ( int , int ) ;

int main () {
	scanf ( "%d%d" , &N , &M ) ;
	for ( int i=0 ; i!=M ; ++i )
		scanf ( "%d%d%d" , &road[i].x , &road[i].y , &road[i].t ) ;
	std::sort ( road , road+M , _cmp ) ;

	for ( int i=0 ; i!=N+1 ; ++i ) f[i]=i ;

	int tem=1;
	for ( int i=0 ; i!=M ; ++i ) {
		int fx=_find(road[i].x) ;
		int fy=_find(road[i].y) ;
		if ( fx!=fy ) {
			f[fx]=fy;
			++tem;
			if (tem==N) {
				printf ( "%d\n" , road[i].t ) ;
				return 0 ;
			}
		}
	}
	printf ( "-1\n" ) ;
	return 0 ;
}

bool _cmp ( Tnode i , Tnode j ) {
	return i.t<j.t;
}

int _find ( int i ) {
	return f[i]==i ? i : ( f[i]=_find(f[i]) ) ;
}

void _union ( int i , int j ) {
	int fi=_find(i) ;
	int fj=_find(j) ;
	if ( fi!=fj ) f[fi] = fj ;
	return ;
}

  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018