• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku1261 Huffman Trees 搜索與數據結構結合的好題

            題意:
            一棵K叉哈弗曼樹,只有中間節點(滿兒子)和葉節點兩種。給出1-k的連續編碼,求出哈弗曼樹的結構。

            解法:
            首先要清楚,哈弗曼編碼是一種沒有公共前綴的編碼,這提供了很重要的剪枝條件
            另外,由于樹中只含有滿節點和空節點(葉子節點),故每分出一個枝條(從葉節點變為一棵子樹)至少增加n-1個葉子節點。
            利用以上兩點,就可以很好的剪枝了。

            剪枝判斷還是通過字典樹(額,這題中似乎叫哈弗曼樹比較合適- -)。詳細看程序吧。

            代碼:
             1    # include <cstdio>
             2    # include <cstring>
             3    # include <vector>
             4    using namespace std;
             5    struct node
             6    {
             7        node *nxt[20];
             8        int count;
             9        bool end;
            10        node()
            11        {
            12            memset(nxt,NULL,sizeof(nxt));
            13            count=0;
            14            end=0;
            15        }

            16    }
            ;
            17    int z,n,count,len,c;
            18    node buffer[100000];
            19    node *head;
            20    char str[250];
            21    int ans[21];
            22    void clear(node *p)
            23    {
            24        memset(p->nxt,NULL,sizeof(p->nxt));
            25        p->end=false;
            26        p->count=0;
            27    }

            28    bool solve(int s,int left,node *p)
            29    {
            30        if(count>z||p->end) return false;
            31        if(s==len&&left==0return true;
            32        else if(left<=0return false;
            33        p->count++;
            34        if(p->count==1)
            35        {
            36            p->end=true;
            37            if(solve(s,left-1,head)) 
            38                {
            39                    ans[z-left+1]=s;
            40                    return true;
            41                }

            42            p->end=false;
            43        }

            44        if(s==len)
            45        {
            46            p->count--;
            47            return false;
            48        }

            49        if(p->count==1) count+=n-1;
            50        if(p->nxt[str[s]-48]==NULL)
            51        {
            52            p->nxt[str[s]-48]=&buffer[c++];
            53            clear(p->nxt[str[s]-48]);
            54        }

            55        if(solve(s+1,left,p->nxt[str[s]-48])) return true;
            56        if(p->count==1) count-=n-1;
            57        p->count--;
            58        return false;    
            59    }

            60    int main()
            61    {
            62        int test;
            63        scanf("%d",&test);
            64        while(test--)
            65        {
            66            c=1;
            67            count=1;
            68            head=&buffer[0];
            69            clear(head);
            70            scanf("%d%d%s",&z,&n,str);
            71            len=strlen(str);
            72            solve(0,z,head);
            73            ans[0]=0;
            74            for(int i=0;i<z;i++)
            75            {
            76                printf("%d->",i);
            77                for(int j=ans[i];j<ans[i+1];j++)
            78                    printf("%c",str[j]);
            79                printf("\n");
            80            }

            81        }

            82        return 0;
            83    }

            posted on 2011-01-11 23:08 yzhw 閱讀(328) 評論(1)  編輯 收藏 引用 所屬分類: searchdata struct

            評論

            # re: pku1261 Huffman Trees 搜索與數據結構結合的好題 2011-01-11 23:26 yzhw

            有一點更正下,不是沒有公共前綴,而是字符的編碼不存在某個編碼是另一個編碼的前綴~  回復  更多評論   

            <2011年7月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            综合久久一区二区三区 | 亚洲成av人片不卡无码久久| 99久久精品免费国产大片| 国内精品久久久久久久影视麻豆| 国产精品99久久久久久董美香| 久久精品中文字幕第23页| 久久精品日日躁夜夜躁欧美| 久久久久高潮毛片免费全部播放| 国产一区二区精品久久| 久久人人爽人人爽人人片AV麻豆 | 精品久久久久久久久久久久久久久| 久久精品18| 久久国产精品成人片免费| 欧美成a人片免费看久久| 久久亚洲AV成人无码国产| 久久精品国产色蜜蜜麻豆| 久久精品毛片免费观看| 亚州日韩精品专区久久久| 久久精品a亚洲国产v高清不卡| 久久久艹| 中文字幕亚洲综合久久| 久久久久人妻一区精品性色av| 久久国产热这里只有精品| 久久久久女人精品毛片| 久久精品极品盛宴观看| 91精品国产色综合久久| 人人狠狠综合久久88成人| 亚洲色欲久久久久综合网| 99久久99久久精品国产| 97久久香蕉国产线看观看| 亚洲AV无码久久精品蜜桃| 国产精品久久久久久久久软件| 久久久久国产精品麻豆AR影院 | 精品乱码久久久久久夜夜嗨 | 久久精品99久久香蕉国产色戒| 久久精品一区二区三区AV| 久久久高清免费视频| 波多野结衣久久一区二区| 久久婷婷五月综合97色直播| 亚洲精品99久久久久中文字幕| 久久中文字幕无码专区|