POJ2513-Colored Sticks

来源:转载

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1304742541

 

大致题意:

给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。

 

解题思路:

可以用图论中欧拉路的知识来解这道题,首先可以把木棒两端看成节点,把木棒看成边,这样相同的颜色就是同一个节点

问题便转化为:

给定一个图,是否存在一笔画”经过涂中每一点,以及经过每一边一次。

这样就是求图中是否存在欧拉路Euler-Path

回顾经典的“七桥问题”,相信很多同学马上就明白了什么是 欧拉路 了,这里不多作解释。

 

由图论知识可以知道,无向图存在欧拉路的充要条件为:

①     图是连通的;

②     所有节点的度为偶数,或者有且只有两个度为奇数的节点。

 

其中①图的连通性用程序判断比较麻烦,先放一下。

这里先说说②关于度数的判断方法:

 

Blue

Magenta

Violet

Cyan

Red

节点的度用颜色出现次数来统计,如样例中,蓝色blue出现三次(不管是出度还是入度),那么blue结点的度就为3,同样地,我们也可以通过输入得到其他全部结点的度,于是,我们有:

Blue=3

Red=2

Violet=1

Cyan=2

Magenta=2

 

 

用一个一维数组就能记录了,然后分别 模2,就能判断颜色结点的奇偶性

只要奇度数的结点数的个数 = 1 或 >=3 ,即使①图连通,欧拉路也必不存在

 

但是若 奇度数的结点数的个数 为0或 ==2,那么我们继续进行①图的连通性证明:

 

证明①图的连通性,使用并查集MergeSet是非常高效的方法。

基本方法:

初始化所输入的n个结点为n棵树,那么就有一个n棵树的森林,此时每棵树的有唯一的结点(根),该结点的祖先就是它本身。再通过不断地输入边,得到某两个结点(集合)之间的关系,进而合并这两个结点(集合),那么这两个集合就构成一个新的集合,集合内的所有结点都有一个共同的新祖先,就是这个集合(树)的根。

最后只要枚举任意一个结点,他们都具有相同的祖先,那么就能证明图时连通的了。

 

但是单纯使用并查集是会超时的,因为这样会导致每次寻找某个结点的祖先时,平均都会花费O(n/2)时间,最坏情况,当n==50W时,O(n/2)大概为25ms,那么要确定50W个结点是否有共同祖先时,总费时为50W*25ms ,铁定超,不算了= =

 

因此必须使用并查集时必须压缩路径,前几次搜索某个结点k的祖先时,在不断通过父亲结点寻找祖先结点时,顺便把从k到最终祖先结点S中经过的所有结点的祖先都指向S,那么以后的搜索就能把时间降低到O(1)

 

由于并查集必须利用 数组的下标 与 存储的对象,使用int是比较方便的处理方法,但是题目的“颜色结点”是string,不方便用来使用并查集,即使用map也不行,虽然STL的map是基于hash的基础上,但并不高效,在本题中使用会超时。

 

为此可以使用Trie字典树,得到每个颜色单词对应的int编号id ,可以说利用Trie把string一一映射到int,是本题后续处理的关键所在。关于动态创建字典树的方法去百度,这里不多说,下面只用用一个图简单说明一下用Trie字典树标识第一个颜色单词blue:


 

这个题目涉及了多个基本数据结构和算法,综合性很强,非常有代表性,能够A到这题确实是受益良多。

 

知识考查点:

1、字典树;

2、欧拉路:其中又考察了判断是否为连通图;

3、并查集 及其优化方法(路径压缩)。

 

输出:

POSSIBLE:  奇度数结点个数==0 或 ==2  且  图连通

IMPOSSIBLE:奇度数结点个数==1 或 >=3  或  图不连通

 

PS:注意创建TrieTree链表时,C++不存在NULL,要用 0 替代 NULL

 1 /* TrieTree + MergeSet + EulerPath*/
2
3 //Memory Time
4 //77460K 2047MS
5
6 #include<iostream>
7 using namespace std;
8
9 const int large=500000; //25W条棒子,有50W个端点
10
11 class TrieTree_Node //字典树结点
12 {
13 public:
14 bool flag; //标记到字典树从根到当前结点所构成的字符串是否为一个(颜色)单词
15 int id; //当前颜色(结点)的编号
16 TrieTree_Node* next[27];
17
18 TrieTree_Node() //initial
19 {
20 flag=false;
21 id=0;
22 memset(next,0,sizeof(next)); //0 <-> NULL
23 }
24 }root; //字典树根节点
25
26 int color=0; //颜色编号指针,最终为颜色总个数
27
28 int degree[large+1]={0}; //第id个结点的总度数
29 int ancestor[large+1]; //第id个结点祖先
30
31
32 /*寻找x结点的最终祖先*/
33
34 int find(int x)
35 {
36 if(ancestor[x]!=x)
37 ancestor[x]=find(ancestor[x]); //路径压缩
38 return ancestor[x];
39 }
40
41 /*合并a、b两个集合*/
42
43 void union_set(int a,int b)
44 {
45 int pa=find(a);
46 int pb=find(b);
47 ancestor[pb]=pa; //使a的祖先 作为 b的祖先
48 return;
49 }
50
51 //利用字典树构造字符串s到编号int的映射
52
53 int hash(char *s)
54 {
55 TrieTree_Node* p=&root; //从TrieTree的根节点出发搜索单词(单词不存在则创建)
56
57 int len=0;
58 while(s[len]!='/0')
59 {
60 int index=s[len++]-'a'; //把小写字母a~z映射到数字的1~26,作为字典树的每一层的索引
61
62 if(!p->next[index]) //当索引不存在时,构建索引
63 p->next[index]=new TrieTree_Node;
64
65 p=p->next[index];
66 }
67
68 if(p->flag) //颜色单词已存在
69 return p->id; //返回其编号
70 else //否则创建单词
71 {
72 p->flag=true;
73 p->id=++color;
74 return p->id; //返回分配给新颜色的编号
75 }
76 }
77
78 int main(void)
79 {
80 /*Initial the Merge-Set*/
81
82 for(int k=1;k<=large;k++) //初始化,每个结点作为一个独立集合
83 ancestor[k]=k; //对于只有一个结点x的集合,x的祖先就是它本身
84
85 /*Input*/
86
87 char a[11],b[11];
88 while(cin>>a>>b)
89 {
90 /*Creat the TrieTree*/
91
92 int i=hash(a);
93 int j=hash(b); //得到a、b颜色的编号
94
95 /*Get all nodes' degree*/
96
97 degree[i]++;
98 degree[j]++; //记录a、b颜色出现的次数(总度数)
99
100 /*Creat the Merge-Set*/
101
102 union_set(i,j);
103 }
104
105 /*Judge the Euler-Path*/
106
107 int s=find(1); //若图为连通图,则s为所有结点的祖先
108 //若图为非连通图,s为所有祖先中的其中一个祖先
109
110 int num=0; //度数为奇数的结点个数
111
112 for(int i=1;i<=color;i++)
113 {
114 if(degree[i]%2==1)
115 num++;
116
117 if(num>2) //度数为奇数的结点数大于3,欧拉路必不存在
118 {
119 cout<<"Impossible"<<endl;
120 return 0;
121 }
122
123 if(find(i)!=s) //存在多个祖先,图为森林,不连通
124 {
125 cout<<"Impossible"<<endl;
126 return 0;
127 }
128 }
129
130 if(num==1) //度数为奇数的结点数等于1,欧拉路必不存在
131 cout<<"Impossible"<<endl;
132 else //度数为奇数的结点数恰好等于2或不存在,存在欧拉路
133 cout<<"Possible"<<endl;
134
135 return 0;
136 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: