HDU 4013 图论树的最小表示-白红宇

HDU 4013 图论树的最小表示

阅读量：2442 次

发布时间：2019-05-10

本文共 3999 字，大约阅读时间需要 13 分钟。

/*******************************************************************************   去年上海赛区热身赛的一道题，树的最小表示模板题。解法就是用二进制枚举所有可能的联通子图，然后求所有联通子图的最小表示，要注意的是对于某一个联通子图，最小表示需要枚举联通子图里的所有的点，然后从这些点开始进行dfs，dfs过程中进入点时，最小表示的字符串+"0"，出点时，最小表示的字符串+"1"，然后对每个点的孩子节点的最小表示进行排序，再接到该点的最小表示的字符串上。*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x) {return x * x;}template 
                                      
                                       T ll(const T & x) {return x << 1;}template 
                                       
                                        T rr(const T & x) {return x << 1 | 1;}template 
                                        
                                         T gcd(T a, T b) { if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXV = 10004;const int MAXN = 200004;int test, n;struct Node{ Node * next[2]; bool end_sign;}trie[MAXN], * const root = trie;int ncnt;VI G[MAXV];bool hs[MAXV];void initTrie(){ ncnt = 1; for (int i = 0; i < 2; ++i) { root->next[i] = NULL; } root->end_sign = false; return ;}Node * createNode(){ for (int i = 0; i < 2; ++i) { trie[ncnt].next[i] = NULL; } trie[ncnt].end_sign = false; return &trie[ncnt++];}bool insertTrie(const string & str){ Node * ptr = root; int len = SC(int, str.length()); for (int i = 0; i < len; ++i) { int t = str[i] - '0'; if (NULL == ptr->next[t]) { ptr->next[t] = createNode(); } ptr = ptr->next[t]; } if (ptr->end_sign) { return false; } ptr->end_sign = true; return true;}void addEdge(int u, int v){ G[u].push_back(v); return ;}void search(int u, int state){ hs[u] = true; for (VI::iterator it = G[u].begin(); it != G[u].end(); ++it) { int v = *it; if ((1 << v) & state) { if (!hs[v]) { search(v, state); } } } return ;}bool connectedJudge(int state){ CLR(hs, false); for (int i = 0; i < n; ++i) { if ((1 << i) & state) { search(i, state); break ; } } for (int i = 0; i < n; ++i) { if ((1 << i) & state) { if (!hs[i]) { return false; } } } return true;}string dfs(int u, string str, int state){ VS vs; hs[u] = true; for (VI::iterator it = G[u].begin(); it != G[u].end(); ++it) { int v = *it; if ((1 << v) & state) { if (!hs[v]) { vs.push_back(dfs(v, "0", state) + "1"); } } } sort(vs.begin(), vs.end()); for (VS::iterator it = vs.begin(); it != vs.end(); ++it) { str += *it; } return str;}bool insertJudge(int state){ bool sign = false; for (int u = 0; u < n; ++u) { if ((1 << u) & state) { CLR(hs, false); if (insertTrie(dfs(u, "", state))) { sign = true; } } } return sign;}void ace(){ int cas = 1; int u, v; int res; for (scanf("%d", &test); test--; ++cas) { scanf("%d", &n); for (int i = 0; i < n; ++i) { G[i].clear(); } initTrie(); for (int i = 0; i < n - 1; ++i) { scanf("%d %d", &u, &v); --u; --v; addEdge(u, v); addEdge(v, u); } res = 0; for (int state = 1; state < (1 << n); ++state) { if (!connectedJudge(state)) { continue ; } if (insertJudge(state)) { ++res; } } printf("Case #%d: %d\n", cas, res); } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...231 21 399 44 31 37 41 65 72 46 8*******************************************************************************/