04-트리 6.Huffman Codes (30)

04-트리 6.Huffman Codes (30)
시간 제한
200 ms
메모리 제한
65536 kB
코드 길이 제한
8000 B
판정 절차
Standard
작자
CHEN, Yue
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 N lines, each in the format:

c[i] code[i]

where c[i] is the i-th character and code[i] is a string of '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.
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

Sample Output:

Yes
Yes
No
No

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void percolateDown(int *heap, int parent) {	//   parent            
	int temp = heap[parent];
	int child = 2 * parent;
	if (child + 1 <= heap[0] && heap[child + 1] < heap[child])
		++child;
	while (child <= heap[0] && heap[child] < temp) {
		heap[parent] = heap[child];
		parent = child;
		child = 2 * parent;
		if (child + 1 <= heap[0] && heap[child + 1] < heap[child])
			++child;
	}
	heap[parent] = temp;
}
void buildMinHeap(int *heap) {			//      ，            
	for (int i = heap[0] / 2; i > 0; --i)	//             
		percolateDown(heap, i);
}
int deleteMin(int *heap) {				//         ，           
	int minElem = heap[1];
	heap[1] = heap[heap[0]--];			//           
	percolateDown(heap, 1);				//               
	return minElem;
}
void insertMinHeap(int *heap, int weight) {			//        
	heap[++heap[0]] = weight;			//      
	//                     ，       （        ）
	for (int i = heap[0] / 2; i > 0 && heap[i] > weight; i /= 2)
		percolateDown(heap, i);
}
int calWPL(int *freq) {
	int heap[100] = {};					//huffman    ，0        ，1        
	int size = 0;
	for (int i = 0; i < 256; ++i) {		//          ，    （       ）
		if (freq[i]) {
			heap[++size] = freq[i];
		}
	}
	heap[0] = size;						//0          
	buildMinHeap(heap);					//  
	//    huffman   ：                    ，     （      ）   ；
	// wpl  =      wpl （          ） +         （          1    ）；
	//       huffman ，           ，             ，wpl       wpl ，      
	int wpl = 0;
	for (int i = 1; i < size; ++i) {
		int weight1 = deleteMin(heap);
		int weight2 = deleteMin(heap);
		wpl += weight1 + weight2;
		insertMinHeap(heap, weight1 + weight2);
	}
	return wpl;
}
int isPrefix(char *s1, char *s2) {		//                
	while (s1 && s2 && *s1 == *s2)		//                 
		++s1, ++s2;
	if (*s1 == '\0' || *s2 == '\0')		//             ，                   
		return 1;
	else
		return 0;
}
int hasPrefixCode(char s[][200], int n) {//  n           
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (isPrefix(s[i], s[j]))	//     
				return 1;
	return 0;
}
int main() {
	freopen("test.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	int freq[256] = {};
	for (int i = 0; i < n; ++i) {
		char ch;
		int num;
		getchar();
		scanf("%c%d", &ch, &num);
		freq[ch] = num;
	}
	int wpl = calWPL(freq);				//    huffman     WPL（     ）
	int k;		//k     
	scanf("%d", &k);
	while (k--) {
		char ch[256];
		char s[256][200];
		int thisWPL = 0;
		for (int i = 0; i < n; ++i) {
			scanf("
%c %s", &ch[i], s[i]);
			thisWPL += freq[ch[i]] * strlen(s[i]);		//           
		}
		if (thisWPL == wpl && !hasPrefixCode(s, n))		//                 ，   huffman  
			printf("Yes
");
		else
			printf("No
");
	}

	return 0;
}
  
제목 링크:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916