现在的位置: 首页 > 综合 > 正文

树形动归 专题

2012年05月19日 ⁄ 综合 ⁄ 共 6449字 ⁄ 字号 小 中 大 ⁄ 评论关闭

直觉上觉得颜色数量不会很多。我就假定最后最多10种颜色。

假定一个root。

f[i][k]表示i为root的子树里i取k色，得到的最小值。

代码

#include<iostream>
#include<cstdio>
#define INF 1000000000
using namespace std;
struct node{
int y,next;
       }E[100001];


int cnt,edg[50001],n,x,y,ans,f[50001][11],NN;
void add_edge(int x,int y)
{
++cnt;E[cnt].y=y;E[cnt].next=edg[x];edg[x]=cnt;
}
int dp(int i,int x,int last)
{
if (f[i][x]!=-1) return f[i][x];

int Min=INF,tt;
        tt=x;
for (int j=edg[i];j!=0;j=E[j].next)
if (E[j].y!=last)
        {
            Min=INF;
for (int k=1;k<=NN;++k) if (k!=x) 
if (dp(E[j].y,k,i)<Min) Min=dp(E[j].y,k,i);
            tt+=Min;
        }

    f[i][x]=tt;
return tt;
}
int main()
{
    freopen("GEMS.in","r",stdin);
    freopen("GEMS.out","w",stdout);
    NN=10;
    scanf("%d",&n);
for (int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
for (int i=1;i<=n;++i) for (int j=1;j<=100;++j) f[i][j]=-1;
    ans=INF;
for (int i=1;i<=NN;++i)
if (dp(1,i,0)<ans) ans=dp(1,i,0);
    cout<<ans<<endl;
return 0;
}

数据生成器

【题目背景】

小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了，于是对原题做了一些扩展：

l       将原题的N从20扩展到200000。

l       将原题经过一条街道需要的时间改为Ti（1 £ Ti £ 1000000000）分钟（i为街道的编号）。

l       增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。

即使这样，他仍然很快地做了出来。于是，小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。

【小明扩展的题目（注意，你并不需要解决此题）】

幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y（因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离），再到大狗家Z，将两份礼物取回。

卡通城由N（3 £ N £ 200000）个居住点和N-1条连接居住点的双向街道组成，经过第i条街道需花费Ti（1 £ Ti £1000000000）分钟的时间。可以保证，任两个居住点间都存在通路。

不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？

【任务描述】

定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。

给出卡通城的地图，找到一组X、Y、Z，使得： 

l       |XY|≤|XZ|

l       |XY|+|YZ|最大。

并求出此时|XY|+|YZ|的值。

【输入文件】

输入文件jerrygen.in第一行是两个整数N（3 £ N £ 200000）和M（M=N-1），分别表示居住点总数和街道总数。从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1£Ui, Vi £ N，1 £ Ti £ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。

【输出文件】

输出文件jerrygen.out仅包含一个整数T，即|XY|+|YZ|的最大值。

【样例输入】

4 3

1 2 1

2 3 1

3 4 1

【样例输出】

4

先假定一个root。

分析一下实质上是求前三长路。fir[i],sec[i],thi[i]分别表示该树根子数下的k短。

from[i]在记录一下fir[i]是用那条路更新的。最后再dfs吧父亲也给考虑下去。

有很多这样先假定树根，少考虑父亲然后最后再线性dfs补充烤炉的题目。

代码

#include<iostream>
#include<cstdio>
#define LL long long
#define N 200001
using namespace std;
struct node{
       LL y,z,next;
       }E[N*2];

LL edg[N],cnt,x,y,z,ans,fir[N],sec[N],thi[N],from[N],vis[N],n,m;
void add_edge(LL x,LL y,LL z)
{
++cnt;E[cnt].y=y;E[cnt].next=edg[x];edg[x]=cnt;E[cnt].z=z;
}
void dp(LL x,LL last,LL tot)
{
// if (vis[x]) return;
//  vis[x]=1;
//  ar[x]=tot;
     LL v;
for (LL j=edg[x];j!=0;j=E[j].next)
if (last!=E[j].y)
     {
         dp(E[j].y,x,tot+E[j].z);
         v=E[j].y;
if (fir[v]+E[j].z>fir[x]) {from[x]=v;thi[x]=sec[x];sec[x]=fir[x];fir[x]=fir[v]+E[j].z;}
else
if (fir[v]+E[j].z>sec[x]) {thi[x]=sec[x];sec[x]=fir[v]+E[j].z;}
else
if (fir[v]+E[j].z>thi[x]) {thi[x]=fir[v]+E[j].z;}
     }
}
void dfs(LL x,LL last,LL tot)
{
if (tot>fir[x]) {from[x]=last;thi[x]=sec[x];sec[x]=fir[x];fir[x]=tot;}
else
if (tot>sec[x]) {thi[x]=sec[x];sec[x]=tot;}
else
if (tot>thi[x]) {thi[x]=tot;}
     LL kk=0;
for (LL j=edg[x];j!=0;j=E[j].next)
if (last!=E[j].y)
     {
          kk=tot;
if (from[x]!=E[j].y && fir[x]>kk) kk=fir[x];  
if (from[x]==E[j].y && sec[x]>kk) kk=sec[x];
          dfs(E[j].y,x,kk+E[j].z);
     }

}
int main()
{
    freopen("jerrygen.in","r",stdin);
    freopen("jerrygen.out","w",stdout);
    scanf("%d%d",&n,&m);
for (LL i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
    dp(1,0,0);
    dfs(1,0,0);
//   for (LL i=1;i<=n;++i)
//   printf("%d %d %d %d\n",i,fir[i],sec[i],thi[i]);
   /*
    for (LL i=1;i<=n;++i)
    {
        if (ar[i]>fir[i]) {thi[i]=sec[i];sec[i]=fir[i];fir[i]=ar[i];}
        else
        if (ar[i]>sec[i]) {thi[i]=sec[i];sec[i]=ar[i];}
        else
        if (ar[i]>thi[i]) {thi[i]=ar[i];}
    } */
//        for (LL i=1;i<=n;++i)
//  printf("*(%d %d %d %d\n",i,fir[i],sec[i],thi[i]);
    for (LL i=1;i<=n;++i)
if (fir[i]+sec[i]*2+thi[i]>ans) ans=fir[i]+sec[i]*2+thi[i];
    cout<<ans<<endl;
return 0;
}

Day 2

(7.18 14:00-19:30)

Tribe council

有一个部族有N个人，这里有一个他们的家族树，1是根节点表示父亲和儿子的关系。节点1是树根。他们要在神圣的山的西边进行一个奇特的会议，就坐在一排桌子旁边，如下图。每个人都尽可能的往前面的桌子坐，如果那个桌子上当前没有他的儿子或者父亲。

现在让你确定一个他们就坐的顺序，使得他们占的桌子数最多。

任务

求能占有的最多桌子数

输入文件 tribe.in

第一行是人数N

以下N-1行每行两个整数x,y，表示x是y的父亲

输出文件tribe.out

把答案输出到文件

数据范围

1<N<=100 000

30%的数据N<=1000

每张桌子有无限的容量

样例

tribe.in

tribe.out

5

1 4

3 2

1 3

3 5

3

解释

样例可以以这种顺序入座 2 4 1 5 3

  • 2 到桌1
  • 4 到桌1
  • 1 有孩子 (4) 在桌1,所以去桌2
  • 5 到桌1
  • 3 有2个孩子在桌1(2 and 5) 而且有父亲 (1)在桌2,所以去桌3.

要求一共能占据多少排，那么就是要使某一个人能坐到尽量靠后的排。在解决问题之前，我们要考虑这样几个问题。假如一个人能坐到第n排，那么他必然能坐到1到n排，因为他坐到第n排的时候，他的相邻点能占据1,2…n-1排，那么让占据1的先坐，然后到占据2的，……。只要他在适当的时候插入，就能坐到1至n排之中的任意一排。另外，如果一个人能坐到第n排，那么他的相邻点一定能分别占据1到n-1排，由于这个点之后才到会，所以之前，每个相邻点都是凭着去掉这个点后的某个子树的人际关系，坐到一个适当位置的。更确切的说，一个点能坐到第n排，按照一定顺序，他的相邻点p1、p2、p3…能坐到的最后排a1、a2、a3……满足a1>=1,a2>=2,a3>=3……。所以在得知一个点的所有相邻点能坐到的最大排后，坐到第一排的肯定用最小的，坐到第二排的肯定用次小的，我们按他们能坐到的最大排来排序，就能很容易的判断一个点能坐到第几排。

这题也是要考虑一个点的各个分叉，我们可以先假设树有一个根，我们先求一个点能凭借它的儿子坐到多少排。然后我们发现，我们没有考虑了一个点通向根的一个分叉，我们需要把漏掉的补上。假设P是Q的父亲节点，P能坐到的最大排已经求出。P要为Q服务，就必须将P的减掉Q这个分支后，再求它坐到的最大排，把P加入Q的相邻点，由于根节点已经完全考虑，我们从根节点往下，就能把所有点求出。-------集训队论文

其实这题跟上题一样都是先假定树根，然后再现不考虑父亲。

最后再dfs一遍补充考虑父亲。

代码

#include<iostream>
#include<cstdio>
#define INF 10000000000
#define N 100001
using namespace std;
struct node{
int  y,next;
       }E[N*2];

int edg[N],x,y,ans,n;
int sum[N][30];
int f[N],cnt;
void add_edge(int x,int y)
{
++cnt;E[cnt].y=y;E[cnt].next=edg[x];edg[x]=cnt;
}
void dp(int x,int last)
{
for (int j=edg[x];j!=0;j=E[j].next)
if (E[j].y!=last)
     {
         dp(E[j].y,x);
++sum[x][f[E[j].y ] ];
     }
int tot=0;
for (int i=1;i<=20;++i) 
     {
         tot+=sum[x][i];if (tot>i) tot=i;
     }
     f[x]=tot+1;
return;
}
void dfs(int x,int last,int mm)
{

int tot=0;

++sum[x][mm];
for (int i=1;i<=20;++i) 
      {
          tot+=sum[x][i];if (tot>i) tot=i;
      }
if (tot+1>ans) ans=tot+1;   // calc_ans
      

for (int j=edg[x];j!=0;j=E[j].next)
if (E[j].y!=last)
     {
--sum[x][ f[E[j].y ] ];

         tot=0;
for (int i=1;i<=20;++i)
         {
             tot+=sum[x][i];if (tot>i) tot=i;
         }

         dfs(E[j].y,x,tot+1);

++sum[x][ f[E[j].y ] ];

     }
}
int main()
{
    freopen("tribe.in","r",stdin);
    freopen("tribe.out","w",stdout);
    scanf("%d",&n);
for (int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }

    ans=0;
    dp(1,0);
for (int i=1;i<=n;++i) if (f[i]>ans) ans=f[i];
    dfs(1,0,0);
    cout<<ans<<endl;
return 0;
}

    选课

[问题描述]

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入：

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=160)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N,1<=si<=20）。

输出：

只有一行，选M门课程的最大得分。

样例：

输入：

7  4

2  2

0  1

0  4

2  1

7  1

7  6

2  2

输出：

13

徐持衡论文。。。。。

代码

#include<iostream>
#include<cstdio>
#define N 1000
using namespace std;
struct node{
int y,next;
       } E[N*2];

int edg[N],ans,s[N],n,x,C,cnt;
int f[N][N];
void add_edge(int x,int y)
{
++cnt;E[cnt].next=edg[x];edg[x]=cnt;E[cnt].y=y;    
}
void dp(int u,int C)
{
if (C<=0) return;
int v;

for (int j=edg[u];j!=0;j=E[j].next)
     {
         v=E[j].y;
for (int i=0;i<=C;++i) f[v][i]=f[u][i];
         dp(v,C-1);
for (int i=0;i<=C-1;++i)
if (f[v][i]+s[v]>f[u][i+1]) f[u][i+1]=f[v][i]+s[v];
     }
}
int main()
{
    freopen("choice.in","r",stdin);
    freopen("choice.out","w",stdout);
    scanf("%d%d",&n,&C);
for (int i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&s[i]);
        add_edge(x,i);
    }
    dp(0,C+1);
for (int i=0;i<=C;++i) if (f[0][i]>ans) ans=f[0][i];
    cout<<ans<<endl;
return 0;
}
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞