3450. Fast Width - #include <Seter> - using namespace Orz;
3450. Fast Width
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于是改了个桶排果然快了不少（应该不能更快了罢）！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #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
评论 (0)