poj 2513 Colored Sticks(并查集+hash+欧拉图)

骑猪看日落 2021-09-15 18:00 237阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> Colored Sticks 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit:&nbsp;5000MS</td> 
 <td>&nbsp;</td> 
 <td>Memory Limit:&nbsp;128000K</td> 
 </tr> 
 <tr> 
 <td>Total Submissions:&nbsp;39375</td> 
 <td>&nbsp;</td> 
 <td>Accepted:&nbsp;10265</td> 
 </tr> 
 </tbody> 
 </table>Description You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color? Input Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks. Output If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible. Sample Input <pre><code>blue red
red violet
cyan blue
blue magenta
magenta cyan
</code></pre> Sample Output <pre><code>Possible</code></pre> Hint Huge input,scanf is recommended. Source <a href="http://poj.org/searchproblem?field=source&amp;key=The+UofA+Local+2000.10.14" rel="nofollow">The UofA Local 2000.10.14</a> </td> 
 </tr> 
 </tbody> 
</table>

\[[Submit][]\]   \[Go Back\]   \[[Status][]\]   \[[Discuss][]\]

标准做法是用并查集+欧拉图+字典树，但是我不想敲字典树

先用了map，毫无意外tle了，然后就想用hash试一下，然后直接过了。。。(不知道那些用map过的到底怎么写的。。。)

个人觉得unordered\_map应该也能过，可惜poj貌似不能用c++11

其实这题最坑的地方是有空输入，这个时候输出possible

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <map>
 
 using namespace std;
 const int maxn = 250010*2;
 
 int sett[maxn];
 int used[maxn];
 
 
 unsigned int hasha(char *url)
 {
 	unsigned int nn=0;
 	char *b=(char *)&nn;
 	for(int i=0;url[i];++i)
 		b[i%4]^=url[i];
 	return nn%maxn;
 }
 
 int findSet(int x)
 {
 if(x==sett[x])
 return x;
 int y = findSet(sett[x]);
 return sett[x] = y;
 }
 
 void unionSet(int x,int y)
 {
 int x1 = findSet(x);
 int y1 = findSet(y);
 if(x1!=y1)
 {
 sett[x1] = y1;
 }
 }
 char str1[15],str2[15];
 int ma[maxn];
 int main()
 {
 int t =0,flag =1;
 for(int i = 0;i<=maxn;i++)
 {
 sett[i] = i;
 used[i] = 0;
 }
 //map<string,int> ma;
 while(scanf("%s%s",str1,str2)!=EOF)
 {
 unsigned int s1 = hasha(str1);
 unsigned int s2 = hasha(str2);
 if(ma[s1]==0)
 ma[s1] = t++;
 if(ma[s2]==0)
 ma[s2] = t++;
 used[ma[s1]]++;
 used[ma[s2]]++;
 unionSet(ma[s1],ma[s2]);
 }
 int k = 0;
 int m = 0;
 for(int i =0;i<t-1;i++)
 {
 if(sett[i] == i)
 {
 m++;
 //cout<<i<<endl;
 }
 if(used[i]%2==1)
 k++;
 }
 //cout<<m<<endl;
 if((k!=0&&k!=2)||m!=1)
 flag = 0;
 if(t==0)
 flag = 1;
 //cout<<flag<<endl;
 if(flag)
 cout<<"Possible"<<endl;
 else
 cout<<"Impossible"<<endl;
 }

[Submit]: http://poj.org/submit?problem_id=2513
[Status]: http://poj.org/problemstatus?problem_id=2513
[Discuss]: http://poj.org/bbs?problem_id=2513