# 05-树9 Huffman Codes（30 分）

In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as {'a'=0, 'x'=10, 'u'=110, 'z'=111}, or in another way as {'a'=1, 'x'=01, 'u'=001, 'z'=000}, both compress the string into 14 bits. Another set of code can be given as {'a'=0, 'x'=11, 'u'=100, 'z'=101}, but {'a'=0, 'x'=01, 'u'=011, 'z'=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

### Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:

``````c[1] f[1] c[2] f[2] ... c[N] f[N]
``````

where `c[i]` is a character chosen from {'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}, and `f[i]` is the frequency of `c[i]` and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of Nlines, each in the format:

``````c[i] code[i]
``````

where `c[i]` is the `i`澳门三合彩票，-th character and `code[i]` is an non-empty string of no more than 63 '0's and '1's.

### Output Specification:

For each test case, print in each line either "Yes" if the student's submission is correct, or "No" if not.

Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.

### Sample Input:

``````7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
``````

5 3
46 23 26 24 10
5 4 3

### Sample Output:

``````Yes
Yes
No
No

``````

``````  1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 #define maxsize 64
5 struct node{
6 int weight=-1;
7 node* l=NULL;
8 node* r=NULL;
9 };
10 using haffmantree=node;
11 vector<node> Minheap;
12 vector<int> no;
13 int size,flag=1;
14 void Createheap(int N){
15 Minheap.resize(N+1);
16 node n; Minheap[0]=n;
17 size=0;
18 }
19 void Insert(node n){
20   int i=++size;
21   for(;Minheap[i/2].weight>n.weight;i/=2)
22   Minheap[i]=Minheap[i/2];
23   Minheap[i]=n;
24 }
26 for(int i=1;i<=N;i++){
27 string str; int num;
28 cin>>str>>num;
29 no.push_back(num);
30 node n;
31 n.weight=num;
32 Insert(n);
33 }
34 }
35 node* Delete(){
36 node* n=new node();
37 n->l=Minheap[1].l;
38 n->r=Minheap[1].r;
39 n->weight=Minheap[1].weight;
40 node temp=Minheap[size--];
41 int parent,child;
42 for(parent=1;parent*2<=size;parent=child){
43 child=2*parent;
44 if(child!=size&&Minheap[child+1].weight<Minheap[child].weight)
45 ++child;
46 if(temp.weight<=Minheap[child].weight) break;
47 else
48 Minheap[parent]=Minheap[child];
49 }
50 Minheap[parent]=temp;
51 return n;
52 }
53 haffmantree huffman(int N){
54     node T;
55 for(int i=1;i<N;i++){
56 node n;
57 n.l=Delete();
58 n.r=Delete();
59 n.weight=n.l->weight+n.r->weight;
60 Insert(n);
61 }
62 T=*Delete();
63 return T;
64 }
65 int WPL(haffmantree T,int depth)
66 {
67 if(T.l==NULL&&T.r==NULL) return depth*(T.weight);
68 else return WPL(*(T.l),depth+1)+WPL(*(T.r),depth+1);
69 }
70 void judge(haffmantree* h,string code){
71 for(int i=0;i<code.length();i++){
72 if(code[i]=='0'){
73 if(h->l==NULL){
74 node* nod=new node();
75 h->l=nod;
76 }
77 else if(h->l->weight>0)
78      flag=0;
79 h=h->l;
80 }
81 else if(code[i]=='1'){
82 if(h->r==NULL){
83 node* nod=new node();
84 h->r=nod;
85 }else if(h->r->weight>0)
86      flag=0;
87     h=h->r;
88 }
89 }
90 if(h->r==NULL&&h->l==NULL)
91 h->weight=1;
92 else flag=0;
93 }
94 int main(){
95 int N; cin>>N;
96 Createheap(N);
98 haffmantree T=huffman(N);
99 int wpl=WPL(T,0);
100 int M; cin>>M;
101 for(int i=1;i<=M;i++){
102 int len=0; haffmantree* h=new node();
103 for(int j=0;j<N;j++){
104 string str,code;
105 cin>>str>>code;
106 judge(h,code);
107 len+=no[j]*code.length();
108 }
109 if(len!=wpl) flag=0;
110 if(flag==1) cout<<"Yes"<<endl;
111 else cout<<"No"<<endl;
112 flag=1;
113 }
114     return 0;
115 }
``````

View Code

24 23 10
46 23 10
26 10

###### Codes:
``````//#define LOCAL#include <cstdio>#define M 1010#define S -10010int i, cnt, A[M] = {S};void insert {    for(i=++cnt; A[i/2]>a; i/=2) A[i] = A[i/2];    A[i] = a;}int main(){    #ifdef LOCAL        freopen("E:\Temp\input.txt", "r", stdin);        freopen("E:\Temp\output.txt", "w", stdout);    #endif    int a, n, m;    scanf("%d%d", &n, &m);    while { scanf("%d", &a); insert; }    while {        scanf("%d", &a);        printf("%d", A[a]); a /= 2;        while { printf(" %d", A[a]); a /= 2; }         printf;     }    return 0;}
``````
##### 05-树8：File Transfer.
###### Description:

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

###### Input:

Each input file contains one test case. For each test case, the first line contains N, the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format: I c1 c2 where I stands for inputting a connection between c1 and c2; or C c1 c2 where C stands for checking if it is possible to transfer files between c1 and c2; or S where S stands for stopping this case.

###### Output:

For each C case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are k components." where k is the number of connected components in this network.

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S