http://www.spoj.pl/problems/FASTW/

在fotile犇的blog(TimeOut...)里看到推荐这题(Orz)。。就去做了下。有点小水啊，就是按W排序后从大到小UNION相应的IJ然后看1与N是否SAME。第一次交的时候按秩合并写错了（今天改的时候才发现！晕！没更新size），BUT加快排还是0.6S水过，但总觉得不够快。看看W<65000于是改了个桶排果然快了不少（应该不能更快了罢）！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int n,m,f[10000],s[10000];
struct edge{
	struct edge *next;
	int i,j;
}*b[65000],st[100000];
fa(x){return f[x]==x?x:(f[x]=fa(f[x]));}
int getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}int main(){
	int i,maxw,minw,t;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)s[f[i]=i]=1;
	st[0].i=getint()-1;st[0].j=getint()-1;
	st[0].next=b[t=getint()];
	b[maxw=minw=t]=st;
	for(i=1;i<m;i++){
		st[i].i=getint()-1;st[i].j=getint()-1;
		st[i].next=b[t=getint()];
		b[t]=st+i;
		if(t>maxw)maxw=t;
		else if(t<minw)minw=t;
	}for(i=maxw;i>=minw;i--){
		for(;b[i];b[i]=b[i]->next){
			s[fa(b[i]->i)]>s[fa(b[i]->j)]?(s[f[f[b[i]->j]]=f[b[i]->i]]+=s[f[b[i]->j]]):(s[f[f[b[i]->i]]=f[b[i]->j]]+=s[f[b[i]->i]]);
			if(fa(0)==fa(n-1))printf("%d\n",i);
			else continue;return 0;
		}
	}puts("0");
	return 0;
}

• inline
• block