• <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)  編輯 收藏 引用 所屬分類: 題目分類:動態規劃
            久久青青草原国产精品免费 | 四虎国产精品成人免费久久| 久久福利青草精品资源站| 品成人欧美大片久久国产欧美| 久久WWW免费人成—看片| 久久人人爽人人人人片av| 中文字幕久久欲求不满| 国产情侣久久久久aⅴ免费| 国产日韩久久久精品影院首页| 久久人妻少妇嫩草AV蜜桃| 久久精品国产半推半就| 色婷婷综合久久久久中文字幕| 国内精品久久久久久野外| 久久午夜福利电影| 欧美777精品久久久久网| 精品一二三区久久aaa片| 狠狠精品干练久久久无码中文字幕| 狠狠综合久久综合88亚洲| 日韩久久久久中文字幕人妻| 国产韩国精品一区二区三区久久| 亚洲级αV无码毛片久久精品| 久久久噜噜噜久久中文字幕色伊伊| 蜜臀av性久久久久蜜臀aⅴ| 久久婷婷五月综合色高清 | 日本国产精品久久| 久久―日本道色综合久久| 久久亚洲精品成人av无码网站| 国产精品久久久香蕉| 一本久道久久综合狠狠躁AV| 欧美激情精品久久久久久久九九九 | 国产真实乱对白精彩久久| 国产精品免费看久久久香蕉| 大伊人青草狠狠久久| 久久免费的精品国产V∧| 国产精品99久久免费观看| 久久夜色精品国产欧美乱| 麻豆一区二区99久久久久| 久久精品中文闷骚内射| 国产精品99久久精品| 久久这里只有精品首页| 国产成人精品久久|