首页 > 代码库 > poj1962(带权并查集)
poj1962(带权并查集)
题目连接:http://poj.org/problem?id=1962
都是套路。。。
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=20010; 4 const int mod=1000; 5 int n; 6 int f[maxn],r[maxn]; 7 8 void init() 9 { 10 for(int i=0;i<=n;i++) 11 { 12 f[i]=i; 13 r[i]=0; 14 } 15 } 16 17 int gf(int x) 18 { 19 if(x!=f[x]) 20 { 21 int t=f[x]; 22 f[x]=gf(t); 23 r[x]+=r[t]; 24 } 25 return f[x]; 26 } 27 28 void uni(int a,int b) 29 { 30 int pa=gf(a); 31 int pb=gf(b); 32 if(pa!=pb) 33 { 34 f[pa]=pb; 35 int x=(a-b)>=0?a-b:b-a; 36 r[pa]=r[b]-r[a]+x%mod; 37 } 38 return ; 39 } 40 41 int main() 42 { 43 int t; 44 scanf("%d",&t); 45 while(t--) 46 { 47 scanf("%d",&n); 48 int x,y; 49 init(); 50 char s[5]; 51 while(scanf("%s",s)) 52 { 53 if(s[0]==‘O‘) break; //看成以0结束,无限tle 54 if(s[0]==‘E‘) 55 { 56 scanf("%d",&x); 57 gf(x); 58 printf("%d\n",r[x]); 59 } 60 if(s[0]==‘I‘) 61 { 62 scanf("%d%d",&x,&y); 63 uni(x,y); 64 } 65 } 66 } 67 }
poj1962(带权并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。