• <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>
            算法學社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            題目描述:
                一棵N(N<5,000)個節點的樹,染兩種顏色,不同顏色不能相鄰且要給盡可能多的節點染色。求顏色A和顏色B可能的染色節點個數。
            算法分析:
                顯然是只有一個節點不染色的時候最優,之前要求出這個節點所有子樹的孩子的個數,這個需要樹形DP。
                然后每個不染色的節點,哪些孩子染哪些顏色,有多少不同的數量,這個是背包。
                然后讓我糾結的是,為啥大家都把背包當水題做?
            #include<iostream>
            #include<cstdio>
            using namespace std;
            const int V = 5005;
            const int E = V<<1;
            int n,e,head[V],nxt[E],pnt[E];
            bool ans[V],dp[V][V];
            void add(int u,int v){
                nxt[e] = head[u]; head[u]=e;pnt[e] = v;e++;
            }
            int sum[V];
            void dfs(int u,int f){
                sum[u] = 1;
                dp[u][0] = 1;
                for(int i=head[u];i!=-1;i=nxt[i]){
                    int v = pnt[i];
                    if(v==f) continue;
                    dfs(v,u);
                    sum[u] += sum[v];
                    for(int i=n-1;i>=0;i--) 
                        if(dp[u][i])
                            dp[u][i + sum[v]] = 1;
                }
                int s = n-sum[u];
                for(int i=n-1;i>=0;i--)
                    if(dp[u][i]) dp[u][i+s] = 1;
            //    cout<<"u: "<<u<<endl;
            //    for(int i=0;i<n;i++) if(dp[u][i]) cout<<i<<" "; cout<<endl;
                for(int i=0;i<n;i++)
                    ans[i] |= dp[u][i];
            }
            int main(){
                scanf("%d",&n);
                for(int i=0;i<n;i++) head[i] = -1;
                int u,v;
                e = 0;
                for(int i=1;i<n;i++){
                    scanf("%d%d",&u,&v);
                    u--; v--;
                    add(u,v);
                    add(v,u);
                }
                dfs(0,0);
                int len = 0;
                for(int i=1;i<n-1;i++)
                    len += ans[i];
                printf("%d\n",len);
                for(int i=1;i<n-1;i++) if(ans[i]){
                    printf("%d %d\n",i,n-1-i);
                }
                return 0;
            }
            posted on 2012-07-21 22:47 西月弦 閱讀(297) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            av无码久久久久久不卡网站| 国产亚洲色婷婷久久99精品| 久久影视国产亚洲| 久久久久亚洲AV片无码下载蜜桃| 久久青青草原亚洲av无码app| 久久精品一区二区三区不卡| 欧美性猛交xxxx免费看久久久| 超级碰碰碰碰97久久久久| 久久综合九色综合网站| 久久精品国产99国产精品 | 久久综合狠狠综合久久激情 | 国产精品伦理久久久久久| 精品伊人久久久| 久久国产精品偷99| 久久久久久夜精品精品免费啦| 精品久久人人做人人爽综合| 久久综合88熟人妻| 国产美女亚洲精品久久久综合| 99久久夜色精品国产网站| 久久亚洲精品成人AV| 欧美久久久久久| 久久久久久亚洲精品无码| 成人久久综合网| 国产精品对白刺激久久久| 久久九九久精品国产免费直播| 久久久久亚洲爆乳少妇无| 久久午夜电影网| 久久精品毛片免费观看| 亚洲av成人无码久久精品| 香蕉久久av一区二区三区| 久久一日本道色综合久久| 狠狠精品久久久无码中文字幕| 伊人久久大香线蕉无码麻豆| 国产99久久久国产精品小说| 久久久久久午夜精品| 久久强奷乱码老熟女网站 | 亚洲午夜久久久久久久久电影网| 亚洲国产成人久久一区久久| 亚洲国产成人久久精品99 | 久久99亚洲综合精品首页| 国产精品丝袜久久久久久不卡|