程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF 23E(Tree-樹-背包合並)

CF 23E(Tree-樹-背包合並)

編輯:C++入門知識

Problem 2 樹(tree.cpp/c/pas) 【題目描述】 L發明了一種與樹有關的游戲(友情提醒:樹是一個沒有環的連通圖):他從樹中刪除任意數量(可以為0)的邊,計算刪除後所有連通塊大小的乘積,L將得到這麼多的分數。你的任務就是對於一顆給定的樹,求出L能得到的最大分數。 【輸入格式】 第一行一個整數n,表示樹的節點個數。   接下來n-1行,每行兩個整數a[i],b[i](1<=a[i],b[i]<=n),表示a[i]與b[i]之間連邊。   保證輸入的圖是一棵樹。 【輸出格式】 輸出一個整數,表示L能得到的最大分數。  【樣例輸入】 樣例1: 5 1 2 2 3 3 4 4 5 樣例2: 8 1 2 1 3 2 4 2 5 3 6 3 7 6 8 樣例3: 3 1 2 1 3 【樣例輸出】 樣例1: 6 樣例2: 18 樣例3: 3 【數據范圍】     對於10%的數據,1<=n<=5;   對於30%的數據,1<=n<=100;   另有30%的數據,保證數據是一條鏈。   對於100%的數據,1<=n<=700;   樹上背包 f[i][j]表示i的父親的連通塊在子樹i中有j個的最大的最大值。 於是這就是樹形Dp+背包合並了、 背包合並2個先合並,再與第三個…… [cpp]  #include<cstdio>   #include<cstring>   #include<algorithm>   #include<functional>   #include<iostream>   #include<cstdlib>   #include<cmath>   using namespace std;   #define MAXN (700+10)   #define ll long long   #define F (100000000)   int n,edge[MAXN*2],pre[MAXN],next[MAXN*2],size=0,son[MAXN];   struct bign   {       ll a[40];       bign(){memset(a,0,sizeof(a));a[0]=1;}       bign(int x){memset(a,0,sizeof(a)); a[0]=1;a[1]=x;   }       ll& operator[](const int i){return a[i];    }       friend bign operator*(bign a,bign b)       {           bign c;           for (int i=1;i<=a[0];i++)               for (int j=1;j<=b[0];j++)               {                   c[i+j-1]+=a[i]*b[j];                   if (c[i+j-1]>F)                   {                       c[i+j]+=c[i+j-1]/F;                       c[i+j-1]%=F;                   }               }           c[0]=min(a[0]+b[0],(long long)39);while (!c[c[0]]&&c[0]>1) c[0]--;           return c;       }        friend bool operator>(bign a,bign b)       {           if (a[0]!=b[0]) return a[0]>b[0];           for (int i=a[0],j=b[0];i>0;i--,j--) if (a[i]!=b[j]) return a[i]>b[j];           return false;              }       void print()       {           printf("%I64d",a[a[0]]);           for (int i=a[0]-1;i;i--)           {               printf("%.8I64d",a[i]);           }       }   }f[MAXN][MAXN];   bign max(bign a,bign b)   {       if (a>b) return a;       return b;   }   void addedge(int u,int v)   {       edge[++size]=v;       next[size]=pre[u];       pre[u]=size;   }   void dfs(int x,int father)   {       son[x]=1;//f[x][1]=1;       f[x][1]=1;       for (int p=pre[x];p;p=next[p])       {           int &v=edge[p];           if (v!=father)           {               dfs(v,x);               /*              for (int i=son[x]+son[v];i>0;i--)              {                  if (i<son[x]) f[x][i]=f[x][i]*son[v];                  for (int k=son[v];k>=0;k--)                      if (i-k-1>=0) f[x][i]=max(f[x][i],f[x][i-k-1]*f[v][k]);                            }              son[x]+=son[v];              bign maxv=son[v];              for (int k=0;k<=son[v]-1;k++) maxv=max(maxv,f[v][k]*(k+1));                                    f[x][0]=f[x][0]*maxv;              */               for (int i=son[x];i;i--)                   for (int j=son[v];j>=0;j--)                       f[x][i+j]=max(f[x][i+j],f[x][i]*f[v][j]);                          son[x]+=son[v];           }       }          f[x][0]=bign(son[x]);       for (int i=1;i<=son[x];i++) f[x][0]=max(f[x][0],f[x][i]*bign(i));                                   return;   }   int main()   {   //  freopen("tree.in","r",stdin);   //  freopen("tree.out","w",stdout);       scanf("%d",&n);       memset(pre,0,sizeof(pre));       memset(next,0,sizeof(next));       for (int i=1;i<n;i++)       {           int u,v;           scanf("%d%d",&u,&v);           addedge(u,v);addedge(v,u);       }       addedge(n+1,1);       dfs(n+1,0); //n+1 is ans       /*      for (int i=1;i<=n+1;i++)      {          for (int j=0;j<=son[i]-1;j++)          {              f[i][j].print();printf(" ");          }          printf("\n");      }      */   //  f[n+1][1]=bign(123456789)*bign(234567899);              f[1][0].print();       printf("\n");              return 0;   }    

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved