「44」最长路

DAG 上的最短路

如果图是有向无环图(DAG)，假设边权是 $w(u,v)$，最长路 DP 写成

$$f[v]=\max_{(u,v)\in E}\{f[u]+w(u,v)\}$$

这和 $\text{DAG}$ 上的最短路求法是一致的。

没有正环的一般图

假设图中不存在正环。我们把所有边权取反：$w'(u,v)=-w(u,v)$

那么对于任意一条路径 $P$，$\sum_{e\in P}w'(e) = -\sum_{e\in P}w(e)$。

因此

$$\max_P \sum_{e\in P}w(e) = -\min_P \sum_{e\in P}(-w(e)).$$

所以在路径集合本身没有变化的前提下：

最长路(w)=−最短路(−w)

一般图

在算法竞赛里说“一般图最长路”，通常指：最长简单路径，即每个顶点最多经过一次。 该问题属于 NP-Hard 问题。

大致的情况如下：

图的情况	常见方法
DAG	拓扑序 DP
树	树的直径 / 树形 DP
一般图，$n\le20$	状压 DP
一般图，$n\approx20\sim30$，稀疏	DFS + 剪枝
一般图，$n$ 很大	必须利用特殊性质
一般图，无特殊性质，$n$ 很大	通常不存在可接受的精确算法

例1

DAG 图求最长路

设 $G$ 为有 $n$ 个顶点的带权有向无环图（DAG），$G$ 中各顶点的编号为 $1$ 到 $n$，请设计算法，计算图 $G$ 中 $1 \sim n$ 间的最长路径。

题目分析

在 DAG 中利用拓扑排序求最长路模版题目，因为只有 $1$ 为起点，所以初始条件为 $d[1] = 0$, 其余节点的 $d$ 值为无穷小。

参考代码

#include <bits/stdc++.h>
using namespace std;

const long long MIN_VAL = -5e9;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> e(n + 1);
    vector<int> deg(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        deg[v]++;
    }

    queue<int> q;
    vector<long long> d(n + 1, -1e18);
    d[1] = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto [y, z] : e[x]) {
            d[y] = max(d[y], d[x] + z);
            deg[y]--;
            if (deg[y] == 0) q.push(y);
        }
    }

    cout << (d[n] < MIN_VAL ? -1 : d[n])  << '\n';
}

例2

「Codeforces 459E」帕什马克与图

给定一张有 $n$ 个顶点和 $m$ 条边的带权有向图。你需要找到一条边数最多的路径（可能不是简单路径），使得边权沿路径严格递增。换言之，路径上每条边的权值都必须严格大于前一条边的权值。

题目分析

为了满足题目中的条件，我们将所有的边按边权以从小到大的方式排列。

处理完所有权值 $\leq w$ 的边之后：

设 $f(i)$ 表示以 $i$ 结尾，且最后一条边的边权 $\le w$ 的路径的经过的最大边数。

如果接下来的边 $(u, v, z)$，边权 $z$ 大于 $w$ 的话，我们可以放心的用 $f[u]$ 去更新 $f[v]$。 $f[v] = f[u] + 1$。

但是，假如接下来的边，边权依然为 $w$，那我们用 $f[u]$ 更新 $f[v]$，可能就会出问题。比如说： 有两条边 $(1, 2, 1)$， $(2, 3, 1)$。利用第一条边，可以得到 $f[2] = 1$。然后利用第二条边，就会错误的将 $f[3]$ 更新为 $f[2] + 1$。

解决办法是分组转移，我们将 $w$ 值相等的边，放在一个组，记录更新的值，但是不保存。具体参考代码实现。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};

int main() {
    int n, m; cin >> n >> m;
    vector<Edge> e(m);
    for (auto &[u, v, w] : e) cin >> u >> v >> w;

    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });

    vector<int> f(n + 1, 0);

    int i = 0;
    while (i < m) {
        int j = i;
        while (j < m && e[j].w == e[i].w) j++;
        vector<pair<int, int>> upd;

        for (int k = i; k < j; k++) {
            auto [u, v, _] = e[k];
            upd.push_back({v, f[u] + 1});
        }

        for (auto [v, val] : upd) {
            f[v] = max(f[v], val);
        }
        i = j;
    }

    cout << *max_element(f.begin(), f.end()) <<details '\n';
}

练习1

「USACO 2006 Open Gold」赶集

每一年，约翰都会带着他的奶牛们去赶集。

集会中一共有 $N$ ($1 \le N\le 400$) 个商店，第 $i$ 个商店会在特定的时间 $P_i$ ($0\le P_i \le 10^9$) 对当时在店里的顾客送出一份精美的礼物。约翰当然得到了这个消息，于是他希望能拿到尽量多的礼物送给他的奶牛们．也就是说，他想尽可能多地在某商店发放礼物的时候，正好呆在店里。

经过一定的调查，约翰弄清楚了从 $i$ 号商店走到 $j$ 号商店所需要的时间 $T_{ij}$ ($1 \le T_{ij}\le 1000000$)。虽然乡间小路奇特的布局使得从 $i$ 号商店走到 $j$ 号商店的最短路不一定是直接连接这两个商店的那条，但约翰并不会选择那些会经过其他商店的路线，只是直接走到目标商店等待礼物的送出。此外，由于约翰爬山的速度总是很慢，$T_{ij}$ 并不一定等于 $T_{ji}$。

约翰在时间 $0$ 时于 $1$ 号商店开始他的旅途．请你帮他设计一条路线来获得尽可能多的礼物。

题目分析

对于图中的一条边 $(u, v, w)$，能够从 $u$ 走到 $v$ 需满足条件 $P[u] + w \le P[v]$。对于这种边，我们才视为真正存在的边。本题等价于从 $1$ 号节点出发，经过真正存在的边，最多能经过多少节点。

注意到环上的边不可能都真正存在，所以本题最终有效的边构成的为 DAG，边长设为 $1$, 使用拓扑 DP 求解最长路即可。

题目要求从 $1$ 号商店出发，但可以不获取 $1$ 号商店的礼品，因此，我们假设一个 $0$ 号节点，因为总是可以获取到 $1$ 号商店的礼品，所以 $0$ 和 $1$ 之间有条长度为 $1$ 的边，$0$ 号节点与其他节点 $x$ 是否存在边长为 $1$ 的边取决与 $1$ 号与 $x$ 的距离和 $P[x]$ 的关系, 即是否满足 $T[1][x] \le P[x]$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> P(n + 1);
    for (int i = 1; i <= n; i++) cin >> P[i];

    vector<int> deg(n + 1);

    vector<vector<int>> e(n + 1); 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t; cin >> t;
            if (i == 1 && t <= P[j]) {
                deg[j]++;
                e[0].push_back(j);
            }

            if (i != j && P[i] + t <= P[j]) {
                deg[j]++;
                // cout << i << " " << j << endl;
                e[i].push_back({j});
            }
            
        }
    }

    queue<int> q;
    vector<int> d(n + 1, -99999);
    for (int i = 0; i <= n; i++) {
        if (deg[i] == 0) q.push(i);
    }
    
    d[0] = 0;
    int ans = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        ans = max(ans, d[x]);
        for (int y : e[x]) {
            deg[y]--;
            // cout << x << " " << y << endl;
            d[y] = max(d[y], d[x] + 1);
            if (deg[y] == 0) q.push(y);
        }
    }
    cout << ans << '\n';
}