poj 2513 Colored Sticks 彩色棒

poj 2513 Colored Sticks

题意：现在有几个木棒，每个木棒端点都着色，问：能否将它们排成一排，同时要满足相邻的的两端点颜色是一样的（一笔画问题）。

trie+并查集+欧拉通路

方法：要想排成一排，可以变向的理解为从一个图里找到一个欧拉通路（一定要想到）；如果只是孤零零的一个个小棒，这道题很难实现。

首先：要先要对所有颜色进行编号，由于事先又不知道有几种颜色，有哪几种颜色。故有一个笨方法，用map<int,string>容器存出现过的颜色，每次在对一个颜色进行编号时要遍历map里的每一个颜色，没有的话添后面，有的话返回颜色所对应的编号。题目中提到颜色最多有500000中颜色，每次查找时最坏的情况是查找次数为500000，会超时。因此这里就要用到trie树，虽然每次也要寻找该颜色是否出现过，但是每次查找最坏情况只是该单词的长度（10），ok？

其次：该题木就可以简化顶点标有序号的一个图，要从中判断有否欧拉通路：1.图是联通的（用并查集判断）2.图中顶点的度要么没有奇数，要么有2个奇数度顶点。

难点：能想到转化为图，找欧拉通路

trie树的另一个作用：编序号！！！！！

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <cmath>
  8 #include <stack>
  9 #include <queue>
 10 #include <functional>
 11 #include <vector>
 12 #include <map>
 13 using namespace std;
 14 #define M 0x0f0f0f0f
 15 #define min(a,b) (a>b?b:a)
 16 #define max(a,b) (a>b?a:b)
 17 int cnt=1;//单词的个数
 18 int father[500002];
 19 int v[500002];
 20 struct tree
 21 {
 22     struct tree *next[30];
 23     int ji;//标记该结点处是否构成单词，还代表该单词的编号
 24 };
 25 int insert_(struct tree *root,char *s)//通过trie树对每一种颜色进行编号
 26 {
 27     int i;
 28     if(*s=='\0'||root==NULL)
 29         return 0;
 30     struct tree *p=root;
 31     while(*s!='\0')
 32     {
 33         if(p->next[*s-'a']==NULL)
 34         {
 35             struct tree *t=(struct tree *)malloc(sizeof(struct tree));
 36             for(i=0; i<30; i++)
 37             {
 38                 t->next[i]=NULL;
 39             }
 40             t->ji=0;
 41             p->next[*s-'a']=t;
 42             p=t;
 43         }
 44         else
 45             p=p->next[*s-'a'];
 46         s++;
 47     }
 48     if(p->ji==0)
 49         p->ji=cnt++;
 50     return p->ji;
 51 }
 52 
 53 //并查集，判断是否联通
 54 void inte()
 55 {
 56     for(int i=0; i<500003; i++)
 57         father[i]=i;
 58 }
 59 
 60 int find_(int a)
 61 {
 62     if(father[a]==a)
 63         return a;
 64     return find_(father[a]);
 65 }
 66 
 67 void unin(int a,int b)
 68 {
 69     int a1=find_(a);
 70     int b1=find_(b);
 71     if(a1!=b1)
 72         father[a1]=b1;
 73 }
 74 
 75 int main()
 76 {
 77     int a1,b1;
 78     char a[13],b[13];
 79     int i;
 80     struct tree *root=(struct tree *)malloc(sizeof(struct tree));
 81     for(i=0; i<30; i++)
 82         root->next[i]=NULL;
 83     root->ji=0;
 84     memset(v,0,sizeof(v));
 85     inte();
 86     while(scanf("%s %s",a,b)!=EOF)
 87     {
 88         a1=insert_(root,a);
 89         b1=insert_(root,b);
 90         v[a1]++;
 91         v[b1]++;
 92         unin(a1,b1);
 93     }
 94     int mm=find_(1);
 95     int flag=0;
 96     int flag1=0;
 97     if(v[1]%2)
 98         flag1++;
 99     for(i=2; i<cnt; i++)
100     {
101         if(mm!=find_(i))
102             flag=1;
103         if(v[i]%2)
104         {
105             flag1++;
106         }
107     }
108 
109     if(flag)//bu lian tong
110         printf("Impossible\n");
111     else if(flag1==0||flag1==2)//ke yibi hua
112         printf("Possible\n");
113     else
114         printf("Impossible\n");
115     return 0;
116 }

View Code