很好的一道题，用到了欧拉图的定义。呃，说实话，大一学的那点关于欧拉图的知识忘得都差不多了，虽然还记得欧拉图，但根本不知道怎么用，怎么判断，记得有次比赛有道题和它很像，当时根本不知道要用什么知识来解决，只是简单的假设着，今天读到这题时，直觉上觉得应该简单的方法，训练计划又提示用trie树，所以认真的推了一个结论，只有当每种颜色的数目都为偶数，或者只有两种颜色的数目为奇数其他的都为偶数时才能完成匹配，当时没想到是欧拉图，所以就按着自己的想法这样做了，可是不对，觉得应该是少了点什么，上网一查才知道这题是用欧拉图，然后又看了一下欧拉图的定义，汗~~
再来说说这道题，题目的意思是，给你一堆木棒，每个木棒的两头都涂有一种颜色，问你如果将涂有相同颜色的木棒的头对在一起，是否能将所有木棒拼成一根。
其实这题就是想问你是否有一种方案可以将每个颜色都访问一遍，也就是欧拉图的定义，在一个连通图中是否可以过每边一次且仅有一次，做起来也很简单，就是先用并查集判断一下图是否连通，然后就是用trie树判断每种颜色出现的数目了，看解题报告中提到他们也用过map集 貌似会超时，没试过，直接用的trie树。
代码：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #define maxx 510006 using namespace std ; struct node { int num ; struct node *next[26]; }*s ; int hash[maxx] , f[maxx] , sum ; struct node *creat ( )//申请空间并初始化 { int i ; struct node *p ; p = ( struct node *) malloc ( sizeof ( struct node )); for ( i = 0 ; i < 26 ; i++ ) p->next[i] = NULL ; p->num = 0; return p ; } void init( )//初始化 { s = creat ( ) ; memset( hash , 0 , sizeof ( hash )); for ( int i = 0 ; i < maxx ; i++ ) f[i] = i ; sum = 0; } int find ( int x )//用并查集判断是否为连通图 { if ( x != f[x] ) f[x] = find ( f[x] ); return f[x] ; } int search ( char str[] )//用trie树标记每种颜色出现的次数 { int len = strlen ( str ); int i ; struct node *p = s ; for ( i = 0 ; i < len ; i++ ) { if ( p->next[str[i]-'a'] == NULL )return 0; p = p->next[str[i]-'a'] ; } return p->num ; } int jud ( )//判断是否可能 { int i ; int ss = 0 ; for ( i = 1 ; i <= sum ; i++ )//判断是否符合欧拉图特性 if ( hash[i] % 2 ) ss++ ; if ( ss != 0 && ss != 2 ) return 0 ; int t = find ( 1 ); for ( i = 2 ; i <= sum ; i++ )//判断图是否连通 if ( t != find ( i )) return 0 ; return 1 ; } void insert ( char str[] , int x )//建树 { int len = strlen ( str ); int i ; struct node *p = s , *q ; for ( i = 0 ; i < len ; i++ ) { if ( p->next[str[i]-'a'] == NULL ) { q = creat( ) ; p->next[str[i]-'a'] = q ; p = q ; } else p = p->next[str[i]-'a'] ; } p->num = x ; } int main() { char str_s[15] , str_t[15] ; init( ) ; while ( scanf ( "%s%s" , str_s , str_t ) != EOF ) { int x = search ( str_s ); int y = search ( str_t ); if ( x == 0 ) insert ( str_s , x = ++sum ); if ( y == 0 ) insert ( str_t , y = ++sum ); hash[x]++ ; hash[y]++ ; int xx = find ( x ); int yy = find ( y ); if ( xx != yy ) f[xx] = yy ; } if ( jud ( ) ) printf ( "Possible\n" ); else printf ( "Impossible\n" ); return 0; }