Cod sursa(job #850197)

Utilizator gicu_01porcescu gicu gicu_01 Data 8 ianuarie 2013 01:56:23
Problema Coduri Huffman Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <string>
#include <fstream>
using namespace std;

ifstream in("huffman.in");
ofstream out("huffman.out");

struct nod{
    int val;
    int left_son;
    int right_son;
    bool x;
}a[2000001];

int n,n2;
long long c[2000001][2];;

void init()
{
    in>>n;
    for (int i=1; i<=n; i++)
    {
        in>>a[i].val;
        a[i].left_son=NULL;
        a[i].right_son=NULL;
        a[i].x=true;
    }
    n2=n;
}

int exract_min()
{
    int p,m=1000000;
    for (int i=1; i<=n; i++)
        if (a[i].val<m  && a[i].x) { m=a[i].val; p=i; }
    a[p].x=false;
    return p;
}

void huffman()
{
    long long x,y,sum=0;
    for (int i=1; i<=n2-1; i++)
    {
        x=exract_min();
        y=exract_min();
        n++;
        a[n].val=a[x].val+a[y].val;
        sum=sum+a[n].val;
        a[n].left_son=x;
        a[n].right_son=y;
        a[n].x=true;
    }
    out<<sum<<endl;
}

void back(int p,long long s,int k)
{
    if (a[p].left_son==NULL) { c[p][0]=k+1; c[p][1]=s; } else
    {
        k++;
        back(a[p].left_son,s*2,k);
        back(a[p].right_son,s*2+1,k);
    }
}

int main()
{
    init();
    huffman();
    //for (int i=1; i<=n; i++) cout<<a[i].val<<" "<<a[i].right_son<<" "<<a[i].left_son<<" "<<a[i].x<<endl;
    back(n,0,-1);
    for (int i=1; i<=n2; i++) out<<c[i][0]<<" "<<c[i][1]<<endl;
    return 0;
}