• <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>

            Sephiroth's boring days!!!

            Love just for you.

            樹歸-珠寶

            【描述】

            給一棵n個結點的樹,給每個點安排一個正整數編號,使得相鄰點具有不同的編號,編號的總和盡量小。
            【輸入】
            第一行:n(n<=50,000)
            以下n-1行,每行兩個數u,v(1<=u,v<=n),表示u 和v有一條邊
            【輸出】
            僅一行,為最小編號和
            【樣例輸入】
            8
            1 2
            1 3
            1 4
            1 5
            5 6
            5 7
            5 8
            【樣例輸出】
            11

            【分析】

            f[i][j]表示i這個點標j這個數所能到達的最小總值。控制j的范圍到30肯定過。

              1: #include <stdio.h>
            
              2: #include <iostream>
            
              3: #define MAXINT 10000000
            
              4: #define maxn 50010
            
              5: using namespace std;
            
              6: 
            
              7: int f[maxn][31];
            
              8: int bl[maxn][maxn/100];
            
              9: int son[maxn][maxn/100],root[maxn];
            
             10: int n;
            
             11: int x,y;
            
             12: int ans=MAXINT;
            
             13: 
            
             14: void maket(int x)
            
             15: {
            
             16:     for (int i=1;i<=bl[x][0];++i)
            
             17:     {
            
             18:         int k=bl[x][i];
            
             19:         if (k==root[x]) continue;
            
             20:         son[x][++son[x][0]]=k;
            
             21:         root[k]=x;
            
             22:         maket(k);
            
             23:     }
            
             24: }
            
             25: 
            
             26: void dp(int x)
            
             27: {
            
             28:     if (f[x][1]) return;
            
             29:     for (int i=1;i<=30;++i)
            
             30:     {
            
             31:         for (int j=1;j<=son[x][0];++j)
            
             32:         {
            
             33:             int tt=son[x][j];
            
             34:             dp(tt);
            
             35:             int minn=MAXINT;
            
             36:             for (int jj=1;jj<=30;++jj)
            
             37:                 if (jj!=i)
            
             38:                     if (f[tt][jj]<minn)
            
             39:                         minn=f[tt][jj];
            
             40:             f[x][i]+=minn;
            
             41:         }
            
             42:         f[x][i]+=i;
            
             43:     }
            
             44: }
            
             45: 
            
             46: int main()
            
             47: {
            
             48:     freopen("gems.in","r",stdin);
            
             49:     freopen("gems.out","w",stdout);
            
             50:     
            
             51:     scanf("%d",&n);
            
             52:     for (int i=1;i<n;++i)
            
             53:     {
            
             54:         scanf("%d%d",&x,&y);
            
             55:         bl[x][++bl[x][0]]=y;
            
             56:         bl[y][++bl[y][0]]=x;
            
             57:     }
            
             58:     maket(1);
            
             59:     dp(1);
            
             60:     for (int i=1;i<=30;++i)
            
             61:         if (f[1][i]<ans)
            
             62:             ans=f[1][i];
            
             63:     printf("%d\n",ans);
            
             64:     return 0;
            
             65: }
            
             66: 

            posted on 2010-09-02 20:40 Sephiroth Lee 閱讀(354) 評論(0)  編輯 收藏 引用 所屬分類: 信息奧賽

            free counters
            波多野结衣久久一区二区| 91精品国产色综合久久| 久久九九免费高清视频| 亚洲人成电影网站久久| 精产国品久久一二三产区区别| 久久久久久久亚洲Av无码| 欧美精品一区二区精品久久| 亚洲精品无码久久不卡| 久久久久久人妻无码| 色偷偷88欧美精品久久久| 亚洲国产精品无码成人片久久| 精品久久久久中文字| 亚洲午夜久久久影院| 美女久久久久久| 久久中文娱乐网| 亚洲综合伊人久久综合| 久久不见久久见免费影院www日本| 国内精品伊人久久久久777| 国产呻吟久久久久久久92| 人妻久久久一区二区三区| 午夜视频久久久久一区| 99久久无码一区人妻| 久久久久久综合一区中文字幕 | 精品无码久久久久久久动漫| 亚洲国产精品无码久久久秋霞2| 热综合一本伊人久久精品| 精品国产乱码久久久久久郑州公司| 伊色综合久久之综合久久| 久久福利片| 久久久久久国产精品免费免费| 久久―日本道色综合久久| 国产精品久久久天天影视| 久久久久久午夜成人影院| 亚洲精品高清国产一线久久| 亚洲va中文字幕无码久久| 国产亚洲精品久久久久秋霞| 久久精品aⅴ无码中文字字幕不卡| 久久精品无码专区免费| 四虎亚洲国产成人久久精品| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久久婷婷五月亚洲97号色 |