文档章节

sgu 149

m2012
 m2012
发布于 2012/05/07 11:52
字数 1652
阅读 127
收藏 0

第一次做树形dp,居然1Y了,而且发现注释真是好东西,写了注释自己也不容易犯错。对于DP来说更是如此,因为DP的状态表述得越不含糊,就越不容易写错转移方程。

 

dp说到底就是递推,往前推或者往后推都不是关键,只要可以推就行。

而树形dp就是推的过程发生树上面。

对于一个点i,假设存在一个距离它最远的一个点j。要从i出发走到j,第一步只有两种可能,要么从i走到i的某个儿子节点,要么从i走到i的父亲。根据这一点,我们可以做个分类:
当第一步是 从i走到i的某个儿子s的时候,接下来,我们要做的就是从s一直往下走,走得越远越好。
当第一步是 从i走到i的父亲f的时候,接下来,我们有3种选择,
(1)我们要么停住不走了
(2)要么就从f走到f的父亲F,然后再从F出发继续走得越远越好。
(3)要么就从f出发,往下走到f的某个儿子k,然后从k出发继续走得越远越好。          (case#)

 很明显,这个过程是一个具有最优质结构的东西。从上面的叙述,我们可以发现,我们需要的信息有:

longestSon[i] 表示从i出发,并且步数不能为0,并且第一步是往下走到某个儿子,能够走到的最远距离
secondlongestSon[i] 表示从i出发,并且步数不能为0,并且第一步是往下走到某个儿子,能够走到的第二远的距离
longestFather[i] 表示从i出发,并且步数不能为0,并且第一步是往上走到i的父亲,能够走到的最远距离

 为什么需要secondlongestSon[i]呢?

因为(case#)有点特殊性,当我们从i走到f以后,如果我们想要继续往下走到f的某个儿子k,很明显,我们要选择一个使得longestSon[k]最大的k,但是这里有个约束条件,就是 k必须不能等于i!
所以呢,如果i恰好就是f的所有儿子里具有最大longestSon的节点,我们也不能令 k = i,这个时候,我们就需要令k 等于 使得longestSon[k]第二最大的k,这就是secondlongestSon[i]的用途。

这题本来以为写起来会很烦,递归就是好,最后写出来发现代码量还可以接受哈

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


// 助手函数 ============== {{{
template<typename T, typename T2>
void makeVector(T & a, int len, const T2 & initV) {
  a.resize(len);
  for (int i = 0; i < a.size(); ++i) a[i] = initV;
}


// ======================= }}}
// 图 =================== {{{
struct Edge {
  int adj;
  Edge* next;
  int length;
};


struct Graph {
  vector<Edge*> vs;

  void init(int pointNum) {
    vs.resize(pointNum);
    for (int i = 0; i < vs.size(); ++i) { vs[i] = NULL; }
  }

  Edge* newEdge() {
    return new Edge;
  }

  void add(int st, int ed, int len) {
    Edge* e = newEdge();

    e->adj = ed;
    e->next = vs[st];
    vs[st] = e;

    e->length = len;

  }

  Edge* get(int i) {
    return vs[i];
  }


};

// ======================= }}}

struct LengthAndId {
  int length;
  int id;
};

inline LengthAndId makeLengthAndId(int L, int id) {
  LengthAndId a;
  a.length = L;
  a.id = id;
  return a;
}

// 全局变量 ======================================

const int infinite = 2000000000;
// longestSon[i] 表示从点i出发,向着它的某个儿子走,走到最长距离,那个时候的目的地。注意的是,目的地必须是自己的真儿子,不能是自己
// 如果这个数为负数,表示它是个叶子,因此一个儿子都没有
vector< LengthAndId > longestSon;
// longestSon[i] 表示从点i出发,向着它的某个儿子走,走到第二最长距离,那个时候的目的地。注意的是,目的地必须是自己的真儿子,不能是自己
// 如果这个数为负数,表示没有第二个儿子
vector< LengthAndId > secondLongestSon;

//longestFather 表示从点i出发向上走,第一步必须是走到它的父亲,然后可以继续走,一直走到最长距离,那个时候的目的地
//如果这个数是负数,表示这个点是整棵大树的根
vector< LengthAndId > longestFather;
vector< int > father; //father[i]表示节点i的父亲节点


const char WHITE = 'W';
const char BLACK = 'B';
const char GRAY = 'G';
vector< char > color;

Graph G; //图
int N;

vector< int > longestFromMe;

// ========================================


struct __CmpByLength {
  bool operator() (const LengthAndId &a, const LengthAndId &b) const {
    return a.length < b.length;
  }
} cmpByLength;


//这个函数计算某个点的longestSon 和 secondLongestSon;
void solve(int me) {
  color[me] = GRAY;

  Edge* e;

  vector<LengthAndId> sons;
  sons.clear();

  for (e = G.get(me); e; e = e->next) {
    if (color[e->adj] != WHITE) continue;
    solve(e->adj);

    if (longestSon[e->adj].length < 0) { //如果那个儿子是个叶节点
      sons.push_back(makeLengthAndId(e->length, e->adj));
    } else {
      sons.push_back(makeLengthAndId(e->length + longestSon[e->adj].length, e->adj));
    }
  }


  if (sons.size() == 0) { //如果没有儿子
    longestSon[me] = makeLengthAndId(-infinite, 0);
    secondLongestSon[me] = makeLengthAndId(-infinite, 0);
  } else if (sons.size() == 1) { //有一个儿子
    longestSon[me] = makeLengthAndId(sons.back().length, sons.back().id);
    secondLongestSon[me] = makeLengthAndId(-infinite, 0);
  } else if (sons.size() >= 2) { //有两个儿子或以上
    sort(sons.begin(), sons.end(), cmpByLength);
    longestSon[me] = makeLengthAndId(sons.back().length, sons.back().id);
    secondLongestSon[me] = makeLengthAndId(sons[sons.size() - 2].length, sons[sons.size() - 2].id);
  }

  color[me] = BLACK;
}

//这个函数计算某个点的longestFather, me 是点的id,len是连接me和父亲的边长度
void solve2(int me, int len) {
  color[me] = GRAY;

  if (father[me] < 0) {
    longestFather[me] = makeLengthAndId(-infinite, 0);
    goto GO_TO_MY_SONS;  //为了避免嵌套太多,用一下goto!
  }

  //当我们从me走到me的父亲的时候,可以有三种选择:停住,继续往上走,往下走(但是不能走回me)
  //停住:
  longestFather[me] = makeLengthAndId(len, father[me]);

  //继续往上走
  if (longestFather[father[me]].length > 0) {
    if (longestFather[me].length < longestFather[father[me]].length + len)
      longestFather[me] = makeLengthAndId(longestFather[father[me]].length + len, father[me]);
  }

  //最复杂的情况,向下走
  //如果me的父亲只有一个节点,就不能向下走
  if (!(secondLongestSon[father[me]].length < 0)) {
    if (longestSon[father[me]].id != me) {
      if (longestFather[me].length < len + longestSon[father[me]].length)
        longestFather[me] = makeLengthAndId(len + longestSon[father[me]].length, father[me]);
    } else {
        if (longestFather[me].length < len + secondLongestSon[father[me]].length)
          longestFather[me] = makeLengthAndId(len + secondLongestSon[father[me]].length, father[me]);
    }
  }




GO_TO_MY_SONS:
  //搞定了自己,可以去搞儿子了
  for (Edge* e = G.get(me); e; e = e->next) {
    if (color[e->adj] != WHITE) continue;
    solve2(e->adj, e->length);
  }



  //这个时候,我们已经有足够信息来知道距离me最远的那个点的距离了!
  longestFromMe[me] = 0;
  if (longestSon[me].length > 0) longestFromMe[me] = longestSon[me].length;
  if (longestFather[me].length > 0 && longestFather[me].length > longestFromMe[me]) longestFromMe[me] = longestFather[me].length;

  //走人!
  color[me] = BLACK;
}



void input() {
  scanf("%d", &N);
  G.init(N + 1);
  makeVector(father, N + 1, 0);
  father[1] = -infinite;
  int i;
  for (i = 2; i <= N; ++i) {
    int f, L;
    scanf("%d %d", &f, &L);
    G.add(f, i, L);
    // G.add(i, f, L);
    father[i] = f;
  }
}


void outputAns() {
  int i;
  for (i = 1; i <= N; ++i) {
    printf("%d\n", longestFromMe[i]);
  }
}

void run() {
  input();
  makeVector(color, N + 1, WHITE);
  makeVector(longestSon, N + 1, makeLengthAndId(0, 0));
  makeVector(secondLongestSon, N + 1, makeLengthAndId(0, 0));
  solve(1);

  makeVector(longestFather, N + 1, makeLengthAndId(0,0));
  makeVector(color, N + 1, WHITE);
  makeVector(longestFromMe, N + 1, 0);
  solve2(1, 0);

  outputAns();
}


int main() {
  run();
  return 0;
}
// vim:foldmethod=marker

© 著作权归作者所有

共有 人打赏支持
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
网络流建模汇总结

因为网上Dinic模板大多不规范或者可以被卡,所以先贴出一份跑得比较快的Dinic模板(主要快在maxflow()里面,可以仔细体会)。 (以下题意请自行百度) 1.最优分配 poj1149 应该是很裸的题了。...

qq_35649707
2017/08/04
0
0
号外!号外!我组调查报告出炉啦

我组调查问卷正式出炉啦!以下是问卷结果信息: 关于华农空教室查询的问卷 1.平常去教学楼自习的频率高吗? [单选题] 选项 小计 比例 高 87 58.39% 只是偶尔 56 37.58% 不喜欢那里,从不去 ...

Triple兔
03/14
0
0
Linux C:system函数与后台作业

system函数的参数(字符串)是要执行的命令,这个命令可以使用 & 运行后台作业,也可以一次执行多个程序。 示例1: 运行结果: 示例2:后台作业 运行结果: 示例3:一次执行多个命令 运行结果...

樂天
2016/03/18
53
0
SGU题目列表(按照AC人数排序)

15509 100 A+B 05909 102 Coprimes 05424 105 Div 3 05024 123 The sum 03552 115 Calendar 03365 135 Drawing Lines 03235 184 Patties 03103 107 987654321 problem 03019 113 Nearly prim......

m2012
2012/04/29
0
0
江苏省各地级市县经纬度查询大全

地名 经度 纬度 卫星经度 方位 俯仰 极化 南京 118.78 32.04 138 146.69 47.28 27.74 江宁 118.83 31.95 138 146.7 47.39 27.77 六合 118.83 32.36 138 147 47 27.39 江浦 118.62 32.07 138......

sinat_34719507
2016/12/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

第11章 多线程

程序、进程、线程 程序(program)是为完成特定任务、用某种语言编写的一组指令的集合。即指一段静态的代码,静态对象。 **进程(process)**是程序的一次执行过程或是正在运行的一个程序。动...

流小文
17分钟前
2
0
SpringBoot引入第三方jar包或本地jar包的处理方式

在开发过程中有时会用到maven仓库里没有的jar包或者本地的jar包,这时没办法通过pom直接引入,那么该怎么解决呢 一般有两种方法 - 第一种是将本地jar包安装在本地maven库 - 第二种是将本地j...

独钓渔
今天
2
0
五、MyBatis缓存

一、MyBatis缓存介绍 缓存的使用可以明显的加快访问数据速度,提升程序处理性能,生活和工作中,使用缓存的地方很多。在开发过程中,从前端-->后端-->数据库等都涉及到缓存。MyBatis作为数据...

yangjianzhou
今天
2
0
最近研究如何加速UI界面开发,有点感觉了

最近在开发JFinal学院的JBolt开发平台,后端没啥说的,做各种极简使用的封装,开发者上手直接使用。 JBolt开发平台包含常用的用户、角色、权限、字典、全局配置、缓存、增删改查完整模块、电...

山东-小木
今天
3
0
《月亮与六便士》的读后感作文3000字

《月亮与六便士》的读后感作文3000字: 看完英国作家威廉.萨默塞特.毛姆所著《月亮与六便士》(李继宏译),第一疑问就是全书即没提到“月亮”,也没提到“六便士”。那这书名又与内容有什么...

原创小博客
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部