# Cod sursa(job #677584)

Utilizator Data 10 februarie 2012 12:50:16 Coduri Huffman 100 cpp done Arhiva educationala 2.22 kb
``````#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 2000005

int N, K;
int qleaf[MAX_N], qint[MAX_N];

int u1, o1, u2, o2;

ll f[MAX_N];
ll val[MAX_N];
int len[MAX_N];
int lf[MAX_N];
int rt[MAX_N];

int getNODE () {
int v1, v2;

if (u1 < o1) v1 = qleaf[u1]; else v1 = MAX_N - 1;
if (u2 < o2) v2 = qint[u2];  else v2 = MAX_N - 1;

if (f[v1] < f[v2]) { ++u1; return v1; }
else  { ++u2; return v2; }
}

void DFS (int node, ll value, int depth) {
if (node < N) {
val[node] = value;
len[node] = depth;

return;
}

DFS (lf[node], value * 2, depth + 1);
DFS (rt[node], value * 2 + 1, depth + 1);
}

int main () {
freopen ("huffman.in", "r", stdin);
freopen ("huffman.out", "w", stdout);

scanf ("%d", &N);
FOR (i, 0, N) {
int frequency;
scanf ("%d", &frequency);

qleaf[o1++] = i;
f[i] = frequency;
}
f[MAX_N - 1] = LLONG_MAX;

K = N;

while (u1 < o1 || o2 - u2 > 1) {
int n1 = getNODE ();
int n2 = getNODE ();

f[K] = f[n1] + f[n2];
lf[K] = n1;
rt[K] = n2;

qint[o2++] = (K++);
}

DFS (K - 1, 0, 0);

ll RESULT = 0;
FOR (i, 0, N) RESULT += len[i] * f[i];

printf ("%lld\n", RESULT);
FOR (i, 0, N) printf ("%d %lld\n", len[i], val[i]);

return 0;
}
``````