【POJ 3522】Slim Span

题目传送门:http://poj.org/problem?id=3522

今天在水位运算生成树,无聊来水一水
很暴力,枚举最大边,然后搞一搞,并查集判树

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100+9;
const int M = 10000+9;
const int INF = 1000000000;

struct Edge{int u,v,w;}e[M];
int n,m,vout,fa[N];

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline int Get_Ans(int lim){
	for (int i=1;i<=n;i++) fa[i] = i;
	fa[e[lim].u] = fa[e[lim].v];
	for (int i=lim-1,t=n-2,f1,f2;i;i--) {
		f1 = find(e[i].u); f2 = find(e[i].v);
		if (f1 != f2) fa[f2] = f1, t--;
		if (!t) return e[i].w;
	}
	return -INF;
}

int main(){
	while (scanf("%d%d",&n,&m) && (n||m)) {
		for (int i=1;i<=m;i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
		sort(e+1,e+1+m); vout = INF;
		for (int lim=m;lim>=n-1;lim--) 
			vout = min(vout, e[lim].w - Get_Ans(lim));
		if (n <= 2) printf("0\n");
		else printf("%d\n",vout>=INF?-1:vout);	
	}
	return 0;
}

2 thoughts to “【POJ 3522】Slim Span”

  1. What i don’t understood is in reality how you’re not actually much more smartly-preferred than you may be right now. You’re very intelligent. You understand therefore considerably in the case of this topic, made me personally believe it from so many varied angles. Its like men and women aren’t involved until it is one thing to accomplish with Girl gaga! Your individual stuffs nice. All the time take care of it up!

Leave a Reply to Naomi Roh Cancel reply

Your email address will not be published. Required fields are marked *