huffman_lab.cpp

#include<bits/stdc++.h>

using namespace std;

#define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
#define mp make_pair
#define pb push_back
#define pii pair<int , int>
#define M 205
#define rep(i , n) for(i = 0 ; i< n ;i++ )
#define repi(i , n ) for(i = 0 ; i<= n ; i++ )
#define mem(x , y ) memset(x , y , sizeof x )
#define mx 5000000
#define ff first
#define ss second

//int dx[] = { -1 ,+1, 0 , 0 , -1 , -1  , 1 , 1 };
//int dy[] = { 0 , 0, +1, -1  , +1 , -1 , 1 , -1 };

//int dx[] = { 1 , 1, 2 , 2  , -1 , -1 , -2 , -2 }; // knight direction
//int dy[] = { 2 , -2, +1, -1 ,2 , -2 , 1 , -1 };


struct myClass{
    char a ;
    int f ;
    myClass(){ f =  -1 ; }
    myClass(char a , int f ){
        this -> a = a ;
        this -> f = f ;
    }
    bool operator<(myClass x) const{ return this-> f > x.f } ;
};


vector<myClass > v ;
vector< int > g[M] , cost[M] ;

map< char , int > m ;
map<myClass , int > track  ;

priority_queue< myClass > pq ;

int par[M]  , vis[M];

void clr(){
int i ;
    rep(i , M ) g[i].clear() ;
    rep(i , M ) cost[i].clear() ;
    rep(i , M) par[i] = i  ;
    if(!pq.empty()) while(!pq.empty() ) pq.pop() ;
    mem(vis , 0 );
    m.clear() ;
    track.clear() ;
}

void dfs(int u ){
    int i ;

    rep(i , g[u].size() ){
        int v =  g[u][i] ;
        if(vis[v ] == -1  ){
            vis[v] = 1 ;
            par[v] = u ;
            dfs( v) ;
        }

    }


}

void huffman(int c ){

int i ,j , k = 0   , var ;
     c = 0 ;
    while(1){
        k=  0 ;
        myClass x =  pq.top() ;

        if(track.find(x) ==  track.end() ) {
            track[x] =  c++ ;
            if(x.f ==  -1 ) m[x.a] = track[x] ;

        }

        pq.pop() ;
        while(!pq.empty()){
            k =  1;
            myClass y =  pq.top() ;  pq.pop() ;

            if(track.find(y) ==  track.end() ) {
                track[y] =  c++ ;
                if(x.f ==  -1 ) m[y.a] = c++;

            }

            int u =  m[x] ;
            int v =  m[y] ;

            myClass node ;
            track[node] = c++ ;
            node.f = x.f + y.f ;
            pq.push(node) ;

            if(x.f < y.f ){
                g[node].pb( x) ; cost[node].pb(0) ;
                g[node].pb( y) ; cost[node].pb(1) ;

            }
            else {
                g[node].pb( x) ; cost[node].pb(1) ;
                g[node].pb( y) ; cost[node].pb(0) ;

            }


        }

        if(k ==  0 ) break ;
    }

    --c ;
    dfs(c) ;

}

int main(){
//  freopen("in.txt", "r",stdin );

    int i , j , k , cs= 0 , tc  , c = 0 ;

    cin >> tc  ;
    while(tc-- ){

        char s[10] ;
        scanf("%s %d" , s , &k );
        printf("%c %d\n", s[0] , k ) ;


        pq.push( myClass(s[0], k)  );

    }
    huffman(c ) ;

    rep(i , n ) printf("%d ", find(i) );

    return 0;
}