1065.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1065 on 2006-01-09 at 18:50:28 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

const int MAX = 32;
const int L_MAX = 1024;
const int INF = 200000000;

class UFSet {
public:
	int parent[MAX], h[MAX];
	void make();
	int find(int);
	void unionSet(int, int);
	pii most();
};
void UFSet::make() {
	memset(parent, -1, sizeof(parent));
	memset(h, 0, sizeof(h));
}
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x), pY = find(y), i;
	if(pX != pY) {
		parent[pX] = pY;
		for(i = 0; i < MAX; i++) {
			if(find(i) == pY) h[i]++;
		}
	}
}

inline int code(char);
pii find(int*);

int main()
{
	UFSet ufs;
	char word[L_MAX];
	int f[MAX], i;
	
	while(gets(word) != NULL && strcmp(word, "END")) {
		int bit = strlen(word)*8, huffman = 0, v = 0;
		memset(f, 0, sizeof(f)); ufs.make();
		for(i = 0; word[i] != 0; i++) {
			if(f[code(word[i])]++ == 0) v++;
		}
		for(i = 1; i < v; i++) {
			pii r = find(f);
			ufs.unionSet(r.first, r.second);
		}
		for(i = 0; word[i] != 0; i++) huffman += ufs.h[code(word[i])];
		if(v == 1) huffman = bit / 8;
		printf("%d %d %.1lf\n", bit, huffman, (double)bit/huffman);
	}

	return 0;
}

inline int code(char c)
{
	if(c == '_') return 26;
	else return (c - 'A');
}
pii find(int* f)
{
	int i, m, sm, vm = INF, svm = INF;
	for(i = 0; i < MAX; i++) {
		if(f[i] < vm && f[i] != 0) vm = f[i], m = i;
	}
	for(i = 0; i < MAX; i++) {
		if(f[i] < svm && f[i] != 0 && i != m) svm = f[i], sm = i;
	}
	f[m] += f[sm]; f[sm] = INF;
	return pii(m, sm);
}