- #include<stdio.h>
- #define len 100000
- struct haha
- {
- int start;
- int l[len];
- int weight;
- }code[100],cd;
- struct xixi
- {
- int weight;
- int parent;
- int l_child;
- int r_child;
- }tree[100];
- int a[300];
- int main()
- {
- int n,k,i,j,m,m1,m2,x1,x2,pare,child;
- while(scanf("%d",&n)!=EOF)
- {
- i=0;
- while(i<n)
- {
- scanf("%d",&k);
- tree[i].weight=k;
- tree[i].l_child=-1;
- tree[i].r_child=-1;
- tree[i].parent=-1;
- i++;
- }
- m=2*n-1;
- for(i=n;i<m;i++)
- {
- tree[i].l_child=-1;
- tree[i].r_child=-1;
- tree[i].parent=-1;
- tree[i].weight=0;
- }
- i=0;
- while(i<n-1)
- {
- m1=m2=1000000000;
- x1=x2=0;
- for(j=0;j<n+i;j++)
- {
- if(tree[j].weight<m1&&tree[j].parent==-1)
- {
- m2=m1;
- x2=x1;
- m1=tree[j].weight;
- x1=j;
- }
- else if(tree[j].weight<m2&&tree[j].parent==-1)
- {
- m2=tree[j].weight;
- x2=j;
- }
- }
- tree[x1].parent=n+i;
- tree[x2].parent=n+i;
- tree[n+i].weight=tree[x1].weight+tree[x2].weight;
- if(x1<x2)
- {
- tree[n+i].l_child=x1;
- tree[n+i].r_child=x2;
- }
- else
- {
- tree[n+i].l_child=x2;
- tree[n+i].r_child=x1;
- }
- i++;
- }
- i=0;
- while(i<n)
- {
- cd.start=n-1;
- child=i;
- pare=tree[child].parent;
- while(pare!=-1)
- {
- if(tree[pare].l_child==child)
- cd.l[cd.start]=0;
- else cd.l[cd.start]=1;
- cd.start--;
- child=pare;
- pare=tree[child].parent;
- }
- for(j=cd.start+1;j<n;j++)
- {
- code[i].l[j]=cd.l[j];
- }
- code[i].start=cd.start+1;
- code[i].weight=tree[i].weight;
- i++;
- }
- i=0;
- while(i<n)
- {
- for (j=code[i].start; j < n; j++)
- {
- printf ("%d", code[i].l[j]);
- }
- printf("\\n");
- i++;
- }
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1811201410985.html
来源: http://www.codesnippet.cn/detail/1811201410985.html