P1807. 最长路

发表于 分类于 阅读次数： Waline： 本文字数： 359 阅读时长 ≈ 1 分钟

考点

  • 拓扑排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int LEN = 5e4 + 50, MIN = 0xc0c0c0c0;
int n, m, tot, head[LEN], dp[LEN], ind[LEN];
queue<int> q;
struct edge {
  int to_, nxt_, w_;
} e[LEN];

void add(int u, int v, int w) {
  e[tot].nxt_ = head[u], e[tot].to_ = v, e[tot].w_ = w;
  head[u] = tot++;
}

void toposort() {
  dp[1] = 0;
  for (int i = 1; i <= n; ++i) {
    if (!ind[i]) {
      q.emplace(i);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = e[i].nxt_) {
      int v = e[i].to_;
      if (dp[u] != MIN) dp[v] = max(dp[v], dp[u] + e[i].w_);
      if (--ind[v] == 0) q.emplace(v);
    }
  }
}

int main() {
  int u, v, w;
  cin >> n >> m;
  memset(head, -1, sizeof(head)), memset(dp, 0xc0, sizeof(dp));
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v >> w;
    add(u, v, w);
    ++ind[v];
  }
  toposort();
  cout << (dp[n] == MIN ? -1 : dp[n]);
  return 0;
}

思路

题目说明了是有向无环图，即DAG，那么就可以使用拓扑排序

设dp[x]为到达结点x的最长路径，可以找到状态转移方程： \[ dp\left[ v \right] =\max \left( dp\left[ v \right] ,dp\left[ u \right] +w \right) ,u\xrightarrow{w}v \] 题目问的仅仅是1到n的最长路径，除1以外的、入度为0的结点为起点的路径就要无视掉

所以令dp[1] = 0，而其他入度为0的结点设置为dp[x] = MIN

这样一来，在决定最大路径时，只要忽略dp[x] == MIN的结点即可

因为拓扑排序是自上而下的，子结点等于MIN只有一种情况，那就是没有访问到