Cod sursa(job #994530)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int Nmax = 1000005;
struct node
{
long long v;
int sons[2];
} Arb[2 * Nmax];
struct cmp
{
bool operator () ( const int &a, const int &b ) const
{
return Arb[a].v > Arb[b].v;
}
};
vector <int> MinHeap;
long long v[Nmax], b[Nmax];
int lg[Nmax];
int N;
long long lungime;
void read()
{
ifstream f("huffman.in");
f >> N;
string FileData( ( istreambuf_iterator <char>( f ) ), istreambuf_iterator<char>( ) );
long long nr = 0;
int index = 1;
uint64_t l = FileData.length();
for ( uint64_t i = 1; i < l; ++i )
if ( isdigit( FileData[i] ) )
nr = nr * 10 + ( FileData[i] - 48 );
else
{
Arb[ index++ ].v = nr;
MinHeap.push_back( index - 1 );
nr = 0;
}
f.close();
}
void solve()
{
int n = N;
for ( int i = 1; i < N; ++i )
{
int ind1, ind2;
ind1 = MinHeap[0];
pop_heap( MinHeap.begin(), MinHeap.end(), cmp() );
MinHeap.pop_back();
ind2 = MinHeap[0];
pop_heap( MinHeap.begin(), MinHeap.end(), cmp() );
MinHeap.pop_back();
n++;
Arb[n].v = Arb[ind1].v + Arb[ind2].v;
Arb[n].sons[0] = ind1;
Arb[n].sons[1] = ind2;
MinHeap.push_back( n );
push_heap( MinHeap.begin(), MinHeap.end(), cmp() );
}
}
void DFS( int root, long long code, int level )
{
if ( Arb[root].sons[0] )
{
DFS( Arb[root].sons[0], 2 * code, level + 1 );
DFS( Arb[root].sons[1], 2 * code + 1, level + 1 );
}
else
{
lg[root] = level;
b[root] = code;
lungime += lg[root] * Arb[root].v;
}
}
inline string number( long long nr )
{
string a;
while ( nr )
{
a.push_back( char( 48 + nr % 10 ) );
nr /= 10;
}
reverse( a.begin(), a.end() );
return a;
}
void print()
{
ofstream g("huffman.out");
string FileOut;
FileOut += number( lungime );
FileOut.push_back( '\n' );
for ( int i = 1; i <= N; ++i )
{
FileOut += number( lg[i] );
FileOut.push_back( ' ' );
FileOut += number( b[i] );
FileOut.push_back( '\n' );
}
g << FileOut;
g.close();
}
int main()
{
read();
make_heap( MinHeap.begin(), MinHeap.end(), cmp() );
solve();
DFS( 2 * N - 1, 0, 0 );
print();
return 0;
}