POJ 2513 Colored Sticks(字典树+并查集连通性+欧拉回路） - c++编程基础

TOP

POJ 2513 Colored Sticks(字典树+并查集连通性+欧拉回路）

2015-07-20 18:02:31 来源: 作者: 【大中小】浏览:2次

题目地址：POJ 2513

刚开始没想到字典树，用的map函数一直TLE，由于上一次的签到题由于没想到字典树而卡了好长时间的深刻教训，于是过了不久就想起来用字典树了，（为什么是在TLE了5次之后。。T^T)然后把map改成了字典树，然后就过了。

这题居然不知不觉的用上了欧拉回路。。其实当时我是这样想的。。因为相互接触的必须要相同，所以除了两端外，其他的都是两两相同的，所以除了两端的颜色外其他的的个数必须为偶数。然后两端的可能相同可能不相同，相同的话，说明所有的都是偶数个数了，不相同的话那就只有这两个颜色个数为奇数。也就是判断保证连通性的同时，只要再保证颜色的个数为奇数的只有0个或两个，由于总个数为偶数，所以这里只要有一个奇数，那肯定还有一个奇数的，不可能存在1个奇数的情况，所以只需要判断是否大于2就行了。赛后才知道原来这就叫欧拉回路。。= = ！

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include
          
            using namespace std; int d[500000], cnt, n, bin[500000]; struct node { int flag; node *next[30]; }; node T[5000000]; node *newnode() { int i; node *p=&T[cnt++]; for(i=0;i<26;i++) { p->next[i]=NULL; } p->flag=0; return p; } int charu(node *root, char *s) { int i, x, len=strlen(s); node *p=root; for(i=0;i
           
            next[x]==NULL) { p->next[x]=newnode(); } p=p->next[x]; } if(p->flag) return p->flag; else { p->flag=++n; return n; } } int find1(int x) { return bin[x]==x?x:bin[x]=find1(bin[x]); } void merger(int x, int y) { int f1=find1(bin[x]); int f2=find1(bin[y]); if(f1!=f2) { if(f2>f1) bin[f2]=f1; else bin[f1]=f2; } } int main() { int i, j, s=0, x=0, x1, x2; char s1[11], s2[11]; memset(d,0,sizeof(d)); for(i=1;i<=500000;i++) { bin[i]=i; } n=0; cnt=0; node *root; root=newnode(); while(scanf("%s%s",s1,s2)!=EOF) { x1=charu(root,s1); x2=charu(root,s2); d[x1]++; d[x2]++; merger(x1,x2); //printf("%d %d\n",x1,x2); } for(i=1;i<=n;i++) { if(d[i]%2) s++; if(s>2) { x=1; break; } } if(x) printf("Impossible\n"); else { int y=0; for(i=1;i<=n;i++) { if(find1(bin[i])!=1) { y=1; break; } } if(y) printf("Impossible\n"); else printf("Possible\n"); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：算法学习 - 后缀表达式（C++ 栈..	下一篇：poj1753,Flip Game

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: