Huffman 인코딩 트리
http://cqsyz.openjudge.cn/hanjai/7/
총 시간 제한: 1000ms
메모리 제한: 65536kB
묘사
n개의 외부 노드를 가진 확충 트리를 구축하고 각 외부 노드 Ki는 이 외부 노드의 권리로 대응하는 Wi가 있다.이 확장 두 갈래 나무의 잎 노드 테이프권 외부 경로 길이를 최소화합니다.
Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)
Wi:각 노드의 권한 값입니다.
Li: 루트 노드에서 i번째 외부 잎 노드까지의 거리입니다.
프로그래밍은 최소 외부 경로의 길이를 계산합니다.
첫 번째 줄을 입력하고 외부 노드의 정수 n을 입력합니다.두 번째 줄은 n개의 정수를 입력하여 각 외부 노드의 값을 대표한다.
2<=N<=100 출력 최소 외부 경로 길이 총계.샘플 입력
4
1 1 3 517하프만 나무를 구축하고 대권 경로와.
#include
#include
#include
using namespace std;
typedef struct node{
int l,r;
int p,w,fa;
bool operatorx.w;
}
}node;
node tr[220];
int main(){
priority_queue q;
int n,w,t;
while(cin>>n){
memset(tr,0,sizeof(tr));
t=0;
while(n--){
cin>>w;
++t;
tr[t]=node{0,0,t,w,0};
q.push(tr[t]);
}
while(q.size()>1){
node x1=q.top();
q.pop();
node x2=q.top();
q.pop();
++t;
tr[t]=node{x1.p,x2.p,t,x1.w+x2.w,0};
tr[x1.p].fa=t;
tr[x2.p].fa=t;
q.push(tr[t]);
}
int ans=0;
for(int i=1;i<=t;i++){
if(tr[i].l==0){
int dep=0;
node x=tr[i];
while(x.fa!=0){
dep++;
x=tr[x.fa];
}
ans+=dep*tr[i].w;
}
}
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
