首页 > 代码库 > poj2513(Colored Sticks)

poj2513(Colored Sticks)

2024-07-15 07:55:48   217人阅读

题目地址：Colored Sticks

 

题目大意：

    给你多个木棒，每个木棒的两头分别着色，使所有木棒首尾排成一条直线，相互接触的端点颜色必须是相同的，问你有没有这种可能性。

 

解题思路：

   先是利用trie树将所给的所有颜色字符串标序。因为是每个木棒只能用一次，简单看成一个木棒的首尾相当于图中的一条连线，将所有数据连通之后，因为每个木棒只能用一次，而且必须都得经过，所以判断是否这个图是否含有无向图的欧拉通路即可。又因为每个木棒不一定在同一集合里，所以需要用并查集来判断无向图是否连通。

 

代码：

  1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 32 /***************************************/ 33 void openfile() 34 { 35     freopen("data.in","rb",stdin); 36     freopen("data.out","wb",stdout); 37 } 38 priority_queue<int> qi1; 39 priority_queue<int, vector<int>, greater<int> >qi2; 40 /**********************华丽丽的分割线,以上为模板部分*****************/ 41 const int MAX=30; 42 const int M=250000+1; 43 struct Trie 44 { 45     Trie *next[MAX];  //存储下一层 46     int v;  //存储到此有多少相同前缀的数目 47     int count; 48 }; 49 Trie *root; 50 int sum; 51 int d=0; 52 int d1[M*2]; 53 int pre[M*2]; 54 int creatTrie(char s[]) 55 { 56     Trie *p,*q; 57     p=root; 58     int len=strlen(s); 59     for(int i=0; i<len; i++) 60     { 61         int ce=s[i]-‘a‘; 62         if (p->next[ce]==NULL) 63         { 64             q=(Trie *)malloc(sizeof(Trie)); 65             q->v=1; 66             for(int j=0; j<MAX; j++) 67             { 68                 q->next[j]=NULL; 69                 q->count=-1; 70             } 71             p->next[ce]=q; 72             p=p->next[ce]; 73         } 74         else 75         { 76             p->v++; 77             p=p->next[ce]; 78         } 79     } 80     p->v=-1; 81     if (p->count==-1) 82         p->count=d++; 83     return p->count; 84 } 85  86 int dealTrie(Trie *T) 87 { 88     if (T==NULL) 89         return 0; 90     for(int i=0; i<MAX; i++) 91         if (T->next[i]!=NULL) 92             dealTrie(T->next[i]); 93     free(T); 94     return 0; 95 } 96 int find(int x) 97 { 98     if (x!=pre[x]) 99     {100         pre[x]=find(pre[x]);101         return pre[x];102     }103     return x;104 }105 void unionone(int a,int b)106 {107     int x=find(a);108     int y=find(b);109     if (x!=y)110         pre[x]=y;111 }112 int main()113 {114     char s1[20],s2[20];115     root=(Trie *)malloc(sizeof(Trie));116     int i,j;117     for(i=0; i<MAX; i++) //初始化118     {119         root->next[i]=NULL;120         root->count=-1;121     }122     for(i=0;i<M;i++)123         pre[i]=i;124     memset(d1,0,sizeof(d1));125     while(scanf("%s %s",s1,s2)!=EOF)126     {127         int a=creatTrie(s1);128         int b=creatTrie(s2);129         unionone(a,b);130         d1[a]++;131         d1[b]++;132     }133     int cnt=0,flag=0;134     for(i=0;i<M*2;i++)135         if (d1[i]%2)136             cnt++;137     if (cnt==2||cnt==0)138         flag=1;139     for(i=0;i<d;i++)140         if (find(0)!=find(i))141             flag=0;142     if (flag)143         printf("Possible\n");144     else145         printf("Impossible\n");146     dealTrie(root);147     return 0;148 }
View Code

 


联系
我们