Pagini recente » Diferente pentru algoritmiada-2013/infoarena-cup/solutii intre reviziile 3 si 1 | Cod sursa (job #2698293)
#include <fstream>
#include <vector>
using namespace std;
ifstream be("huffman.in");
ofstream ki("huffman.out");
const long long inf = 1LL * 1000000000 * 1000000000;
struct node
{
long long freq;
long f[2];
};
void print(int poz,int cod,int level,vector<node>&huff,vector<long>&lg,vector<long long>&b)
{
if(huff[poz].f[0])
{
print(huff[poz].f[0],2*cod,level+1,huff,lg,b);
print(huff[poz].f[1],cod*2+1,level+1,huff,lg,b);
return;
}
lg[poz]=level;
b[poz]=cod;
}
void huffman(vector<node>&huff,vector<vector<long> >&q,vector<long>&lg,vector<long long>&b,long n)
{
long k=n;
long r[2],l[2];
l[0]=l[1]=1;
r[0]=n,r[1]=0;
long long sol=0,min;
long p;
while(l[0]+l[1]<=r[0]+r[1])
{
++k;
for(int j=0;j<2;j++)
{
p=0;
min=inf;
for(int i=0;i<2;i++)
{
if(huff[q[i][l[i]]].freq<min && l[i]<=r[i])
{
p=i;
min=huff[q[i][l[i]]].freq;
}
}
huff[k].f[j]=q[p][l[p]];
huff[k].freq+=huff[q[p][l[p]]].freq;
l[p]++;
}
sol+=huff[k].freq;
q[1][++r[1]]=k;
}
print(k,0,0,huff,lg,b);
ki<<sol<<endl;
}
int main()
{
long n;
be>>n;
vector<node>huff(2*n+100);
vector<long>lg(n+100);
vector<long long>b(n+100);
vector<vector<long> >q(2,vector<long>(n+100));
for(int i=1;i<=n;i++)
{
be>>huff[i].freq;
q[0][i]=i;
}
huffman(huff,q,lg,b,n);
for(int i=1;i<=n;i++)
{
ki<<lg[i]<<" "<<b[i]<<endl;
}
return 0;
}