BZOJ 1083: [SCOI2005]繁忙的都市

starli posted @ 2016年2月14日 19:27 in 最小生成树 , 167 阅读

最小生成树求一下就好了……

其实相当于是二分一个答案然后把所有小于这个权值的边都连上然后判断连通性,但是这个过程其实就是kruscal的过程所以只要最小生成树就可以了

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
struct edge{int a,b,v;}e[N];
int n,m,cnt,ans,f[N];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void Union(int a,int b){f[find(a)]=find(b);}
bool cmp(edge a,edge b){return a.v<b.v;}
int main(){
	//freopen("1083.in","r",stdin);freopen("1083.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(e[i].a)!=find(e[i].b)) cnt++,Union(e[i].a,e[i].b),ans=e[i].v;
		if(cnt==n-1) break;
	}
	printf("%d %d",cnt,ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter