題目描述：
一個哈夫曼樹，給出一個字符串以及編碼，要求確定哈夫曼樹
如果無解或者多解，輸出MULTIPLE TABLES
解法：
同pku1261，那題我寫了詳細的報告，
http://www.shnenglu.com/yzhw/archive/2011/01/11/138368.aspx代碼：
1
# include <cstdio>
2# include <cstring>
3# include <stack>
4using namespace std;
5struct node
6
{
7
int count;
8 node *c[2];
9 node *pre;
10 char end;
11 node()
12
{
13 count=0;
14 c[0]=c[1]=pre=NULL;
15 end=0;
16
}
17
};
18node *head=NULL,*ans[27],*res[27];
19char str[1024],code[1024];
20int count,total;
21bool used[27],hasfind;
22void clear(node *p=head)
23{
24 if(!p) return;
25 clear(p->c[0]);
26 clear(p->c[1]);
27 delete p;
28}
29void init()
30{
31 clear();
32 head=new node();
33 head->count=1;
34 memset(used,0,sizeof(used));
35 memset(ans,0,sizeof(ans));
36 count=2;
37 hasfind=false;
38}
39bool solve(int p1,int p2,node *p=head)
40{
41 if(count>total||p->end) return 0;
42 else if(str[p1]=='\0'&&code[p2]=='\0')
43 {
44 if(!hasfind)
45 {
46 hasfind=true;
47 memcpy(res,ans,sizeof(ans));
48 return 0;
49 }
50 else return 1;
51 }
52 else if(str[p1]=='\0') return 0;
53 else if(str[p1]==' '&&ans[26]||str[p1]!=' '&&ans[str[p1]-'A'])
54 {
55 stack<int> s;
56 node *t=ans[str[p1]==' '?26:str[p1]-'A'];
57 while(t->pre)
58 {
59 s.push(t->pre->c[0]==t?0:1);
60 t=t->pre;
61 }
62 for(;code[p2]!='\0'&&!s.empty();p2++)
63 if(code[p2]==s.top()+48)
64 s.pop();
65 else return 0;
66 if(!s.empty()) return 0;
67 else return solve(p1+1,p2);
68 }
69 else
70 {
71 p->count++;
72 if(p->count==1)
73 {
74 p->end=str[p1];
75 ans[str[p1]==' '?26:str[p1]-'A']=p;
76 if(solve(p1+1,p2)) return 1;
77 p->end=0;
78 ans[str[p1]==' '?26:str[p1]-'A']=NULL;
79 }
80 if(code[p2]=='\0')
81 {
82 p->count--;
83 return 0;
84 }
85 if(p->count==1)
86 count++;
87 if(p->c[code[p2]-'0']==NULL)
88 {
89 p->c[code[p2]-'0']=new node();
90 p->c[code[p2]-'0']->pre=p;
91 }
92 if(solve(p1,p2+1,p->c[code[p2]-'0'])) return 1;
93 if(p->count==1)
94 count--;
95 p->count--;
96 return 0;
97
98 }
99}
100int main()
101{
102 //freopen("ans.txt","w",stdout);
103 int test;
104 scanf("%d",&test);
105 getchar();
106 for(int t=1;t<=test;t++)
107 {
108 init();
109 gets(str);
110 gets(code);
111 total=0;
112 for(int i=0;str[i]!='\0';i++)
113 used[str[i]==' '?26:str[i]-'A']=true;
114 for(int i=0;i<27;i++)
115 total+=used[i];
116 printf("DATASET #%d\n",t);
117 if(solve(0,0)||!hasfind) printf("MULTIPLE TABLES\n");
118 else if(hasfind)
119 {
120 if(used[26])
121 {
122 printf(" = ");
123 stack<int> s;
124 while(res[26]->pre)
125 {
126 s.push(res[26]==res[26]->pre->c[0]?0:1);
127 res[26]=res[26]->pre;
128 }
129 while(!s.empty())
130 {
131 printf("%d",s.top());
132 s.pop();
133 }
134 printf("\n");
135 }
136
137 for(int i=0;i<26;i++)
138 if(used[i])
139 {
140 printf("%c = ",i+65);
141 stack<int> s;
142 while(res[i]->pre)
143 {
144 s.push(res[i]==res[i]->pre->c[0]?0:1);
145 res[i]=res[i]->pre;
146 }
147 while(!s.empty())
148 {
149 printf("%d",s.top());
150 s.pop();
151 }
152 printf("\n");
153 }
154 }
155
156 }
157 return 0;
158}