題意：
一棵K叉哈弗曼樹，只有中間節(jié)點(diǎn)（滿兒子）和葉節(jié)點(diǎn)兩種。給出1-k的連續(xù)編碼，求出哈弗曼樹的結(jié)構(gòu)。
解法：
首先要清楚，哈弗曼編碼是一種沒有公共前綴的編碼，這提供了很重要的剪枝條件
另外，由于樹中只含有滿節(jié)點(diǎn)和空節(jié)點(diǎn)（葉子節(jié)點(diǎn)），故每分出一個(gè)枝條（從葉節(jié)點(diǎn)變?yōu)橐豢米訕洌┲辽僭黾觧-1個(gè)葉子節(jié)點(diǎn)。
利用以上兩點(diǎn)，就可以很好的剪枝了。
剪枝判斷還是通過字典樹（額，這題中似乎叫哈弗曼樹比較合適- -）。詳細(xì)看程序吧。
代碼：
1
# include <cstdio>
2 # include <cstring>
3 # include <vector>
4 using namespace std;
5 struct node
6
{
7
node *nxt[20];
8 int count;
9 bool end;
10 node()
11
{
12 memset(nxt,NULL,sizeof(nxt));
13 count=0;
14 end=0;
15
}
16
};
17 int z,n,count,len,c;
18 node buffer[100000];
19 node *head;
20 char str[250];
21 int ans[21];
22 void clear(node *p)
23 {
24 memset(p->nxt,NULL,sizeof(p->nxt));
25 p->end=false;
26 p->count=0;
27 }
28 bool solve(int s,int left,node *p)
29 {
30 if(count>z||p->end) return false;
31 if(s==len&&left==0) return true;
32 else if(left<=0) return false;
33 p->count++;
34 if(p->count==1)
35 {
36 p->end=true;
37 if(solve(s,left-1,head))
38 {
39 ans[z-left+1]=s;
40 return true;
41 }
42 p->end=false;
43 }
44 if(s==len)
45 {
46 p->count--;
47 return false;
48 }
49 if(p->count==1) count+=n-1;
50 if(p->nxt[str[s]-48]==NULL)
51 {
52 p->nxt[str[s]-48]=&buffer[c++];
53 clear(p->nxt[str[s]-48]);
54 }
55 if(solve(s+1,left,p->nxt[str[s]-48])) return true;
56 if(p->count==1) count-=n-1;
57 p->count--;
58 return false;
59 }
60 int main()
61 {
62 int test;
63 scanf("%d",&test);
64 while(test--)
65 {
66 c=1;
67 count=1;
68 head=&buffer[0];
69 clear(head);
70 scanf("%d%d%s",&z,&n,str);
71 len=strlen(str);
72 solve(0,z,head);
73 ans[0]=0;
74 for(int i=0;i<z;i++)
75 {
76 printf("%d->",i);
77 for(int j=ans[i];j<ans[i+1];j++)
78 printf("%c",str[j]);
79 printf("\n");
80 }
81 }
82 return 0;
83 }