题解 P1113 【杂务】

· · 题解

翻遍了题解，发现各位基本全是拓扑做的，一片拓扑序…… 而我太弱了，完全不知道怎么拓扑……

不过很明显这题是求一个最长路，于是我就只能从1号节点开始搜索…… 不过大爆搜肯定是会TLE的，于是我就加了一个记忆化数组。

因为以一个节点为根的子树的最长路不变且将会被重复使用，就可以写出记忆化搜索。

作为dp的记搜一般是 n^2 的，而一个图是有边作为限制的，所以复杂度大概是 O(m) ，本题 m 最大值小于 10000 * 100 ，可过。

题解中只有一个和我思路相同的，不过他写的是纯dp，而我也不会写dp。

最后挂上 1A 0ms 代码，很简单的~

#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 10000 + 10;
int n, head[maxn], memo[maxn], tim[maxn], edge_num;

struct Edge{ int v, nxt; }edge[100 * maxn];

inline int read() {
  register char ch = 0; register int x = 0;
  while( !isdigit(ch) ) ch = getchar();
  while( isdigit(ch) ) x = (x * 10) + (ch ^ 48), ch = getchar();
  return x;
}

inline void Add_edge(int u, int v) {
  edge[++edge_num].v = v;
  edge[edge_num].nxt = head[u], head[u] = edge_num;
}

int Decade_fripSide(int x) {
  if( memo[x] ) return memo[x];
  if( !head[x] ) return tim[x];
  for(int i = head[x]; i; i = edge[i].nxt)
    memo[x] = max(memo[x], Decade_fripSide(edge[i].v) + tim[x]);
  return memo[x];
}

int main(int argc, char const *argv[])
{
  int v = 0;
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    v = read(), tim[i] = read();
    while( v = read() ) Add_edge(v, i);
  }
  printf("%d\n", Decade_fripSide(1));

  return 0;
}