【POJ 3522】Slim Span



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

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