3450. Fast Width - #include <Seter> - using namespace Orz;

3450. Fast Width

Seter posted @ 2011年8月05日 15:14 in SPOJ with tags Partial DisjointSet , 1341 阅读

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

ID DATE USER PROBLEM RESULT TIME MEM LANG
5471365 2011-08-05 09:09:17 Seter Fast Width 100 
edit  run
0.26 3.2M

C

在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;
}
By Seter
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee