首页 > 代码库 > poj 2513 Colored Sticks (trie 树)
poj 2513 Colored Sticks (trie 树)
链接:poj 2513
题意:给定一些木棒,木棒两端都涂上颜色,不同木棒相接的一边必须是
相同的颜色,求是否能将木棒首尾相接,连成一条直线.
分析:可以用欧拉路的思想来解,将木棒的每一端都看成一个结点
由图论知识可以知道,无向图存在欧拉路的充要条件为:
① 图是连通的;
② 所有节点的度为偶数,或者有且只有两个度为奇数的结点。
图的连通性可以用并查集,因为数据比较大,所以用并查集时要压缩路径,
所有节点的度(入度和出度的和)用数组记录就好
但是25w个木棒,有50w个结点,要怎么存呢,如果用数组,每次得查找,
效率特别低,这样就可以用trie树存储数据,用空间换取时间
#include<stdio.h> #include<string.h> #include<stdlib.h> #define M 500000 typedef struct stu { int id,flag; //id为结点的编号,flag标记改颜色是否存在 struct stu *next[26]; }node; int num=1,f[M+5],d[M+5]; node* creat_node() //创建结点并初始化 { node *p=(node*)malloc(sizeof(node)); p->id=p->flag=0; memset(p->next,0,sizeof(p->next)); return p; } int trie_insert(node *p,char *s) //插入颜色结点,并返回其编号 { int i; while(*s!='\0'){ i=*s-'a'; if(p->next[i]==NULL) p->next[i]=creat_node(); p=p->next[i]; s++; } if(!p->flag){ p->flag=1; p->id=num++; } return p->id; } int find(int x) //并查集查找,并压缩路径 { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void mix(int a,int b) //并查集的合并 { a=find(a); b=find(b); if(a!=b) f[a]=b; } int main() { int i,j,n,m,flag=1; node *root=NULL; char s1[15],s2[15]; root=creat_node(); //创建根结点 for(i=1;i<=M;i++){ //父节点以及度的初始化 f[i]=i; d[i]=0; } while(scanf("%s%s",s1,s2)!=EOF){ i=trie_insert(root,s1); j=trie_insert(root,s2); mix(i,j); d[i]++; d[j]++; } m=n=0; for(i=1;i<num&&flag;i++){ if(d[i]%2) n++; //记录度为奇数的结点 if(n>2) flag=0; if(f[i]==i) //记录公共祖先结点的个数 m++; if(m>1) flag=0; } if(flag) printf("Possible\n"); else printf("Impossible\n"); return 0; }
poj 2513 Colored Sticks (trie 树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。