首页 > 代码库 > poj 2513 Colored Sticks 彩色棒

poj 2513 Colored Sticks 彩色棒

2024-07-15 12:44:51   218人阅读

poj  2513  Colored Sticks

http://poj.org/problem?id=2513

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

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 tong110         printf("Impossible\n");111     else if(flag1==0||flag1==2)//ke yibi hua112         printf("Possible\n");113     else114         printf("Impossible\n");115     return 0;116 }
View Code

 

        

                


联系
我们