• <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 閱讀(360) 評論(0)  編輯 收藏 引用 所屬分類: 信息奧賽

            free counters
            99久久亚洲综合精品网站| 久久精品人人做人人爽97| 久久国产福利免费| 久久青青色综合| 99久久成人国产精品免费| 久久久91人妻无码精品蜜桃HD| 四虎影视久久久免费观看| 久久久久久亚洲精品成人| 久久婷婷五月综合色99啪ak | 熟妇人妻久久中文字幕| 久久精品中文字幕久久| 久久久久高潮综合影院| 久久久久久亚洲精品无码| 人妻丰满AV无码久久不卡| 蜜臀久久99精品久久久久久| 国产精品99久久精品| 久久久久免费看成人影片| 亚洲日本va午夜中文字幕久久 | 欧美亚洲国产精品久久蜜芽| 中文字幕无码久久久| 精品久久人人爽天天玩人人妻| 亚洲国产精品无码久久久蜜芽| 日本亚洲色大成网站WWW久久| 91久久九九无码成人网站| 丰满少妇人妻久久久久久| 久久香综合精品久久伊人| 久久久久久久波多野结衣高潮| 色悠久久久久久久综合网| 久久国产福利免费| 久久伊人五月天论坛| 久久精品国产第一区二区| 久久亚洲国产精品123区| 国产三级精品久久| 久久久久人妻精品一区三寸蜜桃 | yy6080久久| 久久九九久精品国产免费直播| 久久夜色精品国产亚洲| 无码日韩人妻精品久久蜜桃| 久久综合国产乱子伦精品免费| 亚洲AV无码久久精品狠狠爱浪潮| 亚洲人成网亚洲欧洲无码久久|