Cod sursa(job #461317)

Utilizator BitOneSAlexandru BitOne Data 6 iunie 2010 12:23:46
Problema Coduri Huffman Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <map>
#include <cstdlib>
#include <fstream>
#define Nmax 2000011
#define oo 10000000000000000LL

/*
 *
 */
using namespace std;
typedef long long int lld;
typedef pair< lld, int > pr;
struct tree
{
    lld Cost;
    int left, right;
    tree( void ) : Cost(oo), left(0), right(0) {}
    tree( lld _Cost, int _left, int _right ) : Cost(_Cost), left(_left), right(_right) {}
} t[Nmax];
multimap< lld, int > v;
ofstream out( "huffman.out" );
inline void OutPut( int x, lld cod, lld idx )
{
    if( 0 == t[x].left )
    {
        out<<idx<<' '<<cod<<'\n';
    }
    else {
            OutPut( t[x].left, 2*cod, idx+1 );
            OutPut( t[x].right, 2*cod+1, idx+1 );
         }
}
int main( void )
{
    lld s;
    pr x, y;
    int N, i, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>j;
        v.insert( pr( j, i ) );
    }
    for( s=0; v.size() > 1; ++i )
    {
        x=*(v.begin());
        v.erase( v.begin() );
        y=*(v.begin());
        v.erase( v.begin() );
        t[x.second].Cost=x.first;   t[y.second].Cost=y.first;
        s+=( t[i].Cost=x.first+y.first );
        t[i].left=x.second;         t[i].right=y.second;
        v.insert( pr( t[i].Cost, i ) );
    }
    out<<s<<'\n';
    OutPut( i-1, 0, 0 );
    return EXIT_SUCCESS;
}