• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            題目描述
            農夫John的農場有n(n<=150)個牛舍,有些牛舍之間有雙向道路連接,而每兩個牛舍之間有且僅有一條道路(因此可以表示成一棵樹)。由于任意一場地震都很可能讓John的農場變得不連通,因此John希望估計一下,至少需要毀壞多少條道路才會讓一個恰好有p(p<=n)個牛舍的子樹脫離其他牛舍。

            此題采用樹型動態規劃求解。
            1、建樹
            由于一個結點可能會有多個子結點,給下面的動態規劃帶來不便,所以采用“左兒子右兄弟”表示法。
            2、狀態定義
            定義d(i,j)表示在i結點上選取它的兒子或右邊的兄弟或右邊的兄弟的兄弟……共j個(包含自身)至少需要毀壞的道路數。
            3、狀態轉移方程
            考慮幾種決策:
            i結點連同所有兒子結點都舍棄不用:d(i,j)=d(R(i),j)+1;
            i結點由包含k個結點的左子樹和j-k-1個結點的右子樹組成:d(i,j)=d(L(i),k)+d(R(i),j-k-1);
            4、邊界條件
            為了方便處理,如果一個結點沒有左兒子或右兒子(在轉換之后的二叉樹中),那么它的左兒子或右兒子為0號結點。
            那么邊界可以是:
            d(0,0)=0;
            d(0,i)=INF,1<=i<=n;
            我覺得這種表示還是很巧妙的。
            注意,即使以i結點為根的數左子樹為空,也不一定毀壞一條道路就能剪掉整個左子樹,因為這是轉換了之后的二叉樹,原樹上i結點可能有眾多子結點。
            5、最優解
            在d(L(i),p-1)+(i==root?0:1)中找最優解。因為如果i是根節點,不需要毀壞任何道路。

            以下是我的代碼:
            #include<fstream>
            #include
            <string.h>
            #define maxn 157
            #define INF 20000007
            using namespace std;
            long min(long a,long b){return (a<b?a:b);}

            typedef 
            struct
            {
                
            long ls,rs;
            }treenode;

            long n,p,root,ans,father[maxn],d[maxn][maxn];
            treenode tree[maxn];

            void Insert(long u,long v)
            {
                
            if(!tree[u].ls)
                    tree[u].ls
            =v;
                
            else
                {
                    
            long p;
                    
            for(p=tree[u].ls;tree[p].rs;p=tree[p].rs);
                    tree[p].rs
            =v;
                }
            }

            long dp(long i,long j)
            {
                
            if(d[i][j]!=-1return d[i][j];
                d[i][j]
            =dp(tree[i].rs,j)+1;
                
            for(long k=0;j-k-1>=0;k++)
                    d[i][j]
            =min(d[i][j],dp(tree[i].ls,k)+dp(tree[i].rs,j-k-1));
                
            return d[i][j];
            }

            int main()
            {
                ifstream fin(
            "roads.in");ofstream fout("roads.out");
                
                memset(tree,
            0,sizeof(tree));
                memset(father,
            0,sizeof(father));
                fin
            >>n>>p;
                
            for(long i=1;i<=n-1;i++)
                {
                    
            long u,v;
                    fin
            >>u>>v;
                    Insert(u,v);
                    father[v]
            =u;
                }
                
            //  Input
                
                memset(d,
            -1,sizeof(d));
                
            for(long i=1;i<=n;i++)
                    d[
            0][i]=INF;
                d[
            0][0]=0;
                
            //  Init
                
                
            for(long i=1;i<=n;i++)
                    
            if(!father[i])
                        root
            =i;
                
            //  Find root
                
                ans
            =INF;
                
            for(long i=1;i<=n;i++)
                  ans
            =min(ans,dp(tree[i].ls,p-1)+(i==root?0:1));
                fout
            <<ans<<endl;
                
            //  Output
                
                fin.close();fout.close();
            return 0;
            }
            posted on 2010-10-11 22:47 lee1r 閱讀(576) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:動態規劃
            亚洲成人精品久久| 色老头网站久久网| 国产亚洲欧美成人久久片| 国内精品久久久人妻中文字幕| 99久久人妻无码精品系列 | 国产精品伊人久久伊人电影 | 亚洲国产精品无码久久一线| 99久久这里只精品国产免费| 亚洲乱码精品久久久久.. | 久久精品亚洲男人的天堂 | 久久国产精品99精品国产987| 99久久精品无码一区二区毛片| 久久精品国产亚洲精品| 中文字幕久久波多野结衣av| 91久久香蕉国产熟女线看| 一本色综合久久| 久久成人国产精品免费软件| 亚洲欧美日韩精品久久亚洲区 | 久久99久久99精品免视看动漫 | 久久久久国产精品嫩草影院| 久久久久国产精品熟女影院 | 国产精品一久久香蕉国产线看观看| 丰满少妇人妻久久久久久| 久久国产精品一区| 国产精品对白刺激久久久| 性欧美大战久久久久久久| 亚洲精品tv久久久久久久久| 久久精品夜色噜噜亚洲A∨ | 久久精品视频一| 久久99精品久久久久久齐齐| 国内精品久久久久| 久久久亚洲欧洲日产国码二区 | 久久久久久久综合日本亚洲| A级毛片无码久久精品免费| 久久精品无码一区二区三区日韩 | 美女久久久久久| 狠狠色婷婷综合天天久久丁香| 亚洲国产欧洲综合997久久| 精品无码久久久久国产动漫3d| 色播久久人人爽人人爽人人片aV| 国产精品久久影院|