首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

CF 23E(Tree-树-双肩包合并)

2013-03-27 
CF 23E(Tree-树-背包合并)Problem 2 树(tree.cpp/c/pas)【题目描述】L发明了一种与树有关的游戏(友情提醒:树

CF 23E(Tree-树-背包合并)

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个先合并,再与第三个……

#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;}


热点排行