P1073 [NOIP 2009 提高组] 最优贸易 题解

题目大意

一张图中有若干有向边和若干无向边，第 $i$ 个节点有一个价格 $p[i]$，对于所有的路径 $1 \rightarrow u \rightarrow v \rightarrow n$（$1,u,v,n$ 可以相等），求 $p[v] - p[u]$ 的最大值。

分析与实现

点击标题以跳转到完整代码

朴素做法

设价格最大值为 $K$，我们高兴地发现 $K \le 100$，于是 $\mathrm O(NK)$ 的做法可以通过本题。

我们可以考虑一种贪心：枚举 $1$ 可达的买入节点（$u$）并选择卖出节点（$v$），使得 $u$ 可达 $v$、$v$ 可达 $n$ 且 $v$ 的价格（$p[v]$）最大。

注：我们称 $u$ 可达 $v$ 当且仅当存在路径 $u \rightarrow v$。

由于我们实际上只关心价格，因此对于某一结点 $u$，所有可达的价格相同的节点都是等价的，于是我们只需要维护 $u$ 到每种价格节点的可达性，然后直接枚举所有可能的价格 $k$ 来更新答案。

接下来考虑具体实现，因为只需要维护可达性，可以用 BFS 或 DFS 来实现，为了方便，接下来的实现全部使用 BFS。

值得注意的是，使用 BFS 维护「所有节点到某一结点的可达性」必须要建反图，因为 BFS 只能用前驱节点更新后继节点，不像 DFS 可以通过回溯的方式用后继节点更新前驱节点，因此必须要将其转化为「某一结点到所有节点的可达性」。

且慢……，如果我们以每一个节点为原点跑 BFS，那么复杂度不就达到 $\mathrm O(N^2)$ 了吗？

但是还记得我说过吗？所有可达的价格相同的节点都是等价的，于是我们就可以请出「多源 BFS」，即一开始将所有价格为 $k$ 的节点压入队列。枚举所有的价格跑 BFS，就能在 $\mathrm O(NK)$ 的复杂度下实现了。

具体地，考虑路径 $1 \rightarrow u \rightarrow v(p[v]=k) \rightarrow n$ 我们需要维护三个可达性，分别是 $1 \rightarrow u$、$u \rightarrow v(p[v]=k)\color{grey}(\rightarrow n)$ 和 $v \rightarrow n$，这里使用三个 BFS 来实现：

注意我们在买入点考虑卖出价格时，要保证能够到达终点，因此要维护 $u \rightarrow v(p[v]=k) \rightarrow n$。

// un[u]: u -> n 
// ukn[k][u] u -> v(p[v] == k) -> n
// ou[u]: one -> u

#define Push(st, x) if(!st[x]) st[x] = 1, q.push(x)
void bfs_n() {
    queue<int> q;
    Push(un, n);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int v : H[u]) Push(un, v);
    }
}
void bfs_k(int k) {
    queue<int> q;
    for(int u = 1; u <= n; u++)
        if(un[u] && p[u] == k) Push(ukn[k], u);
    while(q.size()) {
        int u = q.front(); q.pop();
         for(int v : H[u]) Push(ukn[k], v);
    }
}
void bfs_1() {
    queue<int> q;
    Push(ou, 1);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int k = 1; k < K; k++)
            if(ukn[k][u]) ans = max(ans, k - p[u]);
        for(int v : G[u]) Push(ou, v);
    }
}

其中 G 为正图而 H 为反图。

注意在 bfs_1() 中对于每一个 $1$ 可达的节点枚举价格更新答案。

这里实际上有一个显然的（同时也是符合贪心策略的）优化：

    for(int k = 1; k < K; k++)
        if(ukn[k][u]) ans = max(ans, k - p[u]);

可以改为

    for(int k = K - 1; k; k--)
        if(ukn[k][u]) { ans = max(ans, k - p[u]); break; }

贪心优化

容易发现，对于一个节点 $u$，我们其实并没有必要维护其到每种价格节点的可达性，根据刚才的贪心策略，我们实际上只需要维护 $u$ 可达节点的最大价格。

我们可以用一个 $mx[u]$ 来维护 $u$ 可达节点的最大价格，从大到小枚举 $k$ 跑 BFS，如果遇到 $mx[v] > k$，那么就不将该节点压入队列。这样一来，每个节点在 BFS 中最多入队一次，复杂度就来到了 $\mathrm O(N+K)$，bfs_k() 和 bfs_1() 实现如下：

void bfs_k(int k) {
	queue<int> q;
    for(int u = 1; u <= n; u++)
        if(un[u] && p[u] == k && mx[u] < k) mx[u] = k, q.push(u);
	while(q.size()) {
		int u = q.front(); q.pop();
 		for(int v : H[u]) if(mx[v] < k) mx[v] = k, q.push(v);
	}
}
void bfs_1() {
	queue<int> q;
	ou[1] = 1, q.push(1);
	while(q.size()) {
		int u = q.front(); q.pop();
		ans = max(ans, mx[u] - p[u]);
		for(int v : G[u]) if(!ou[v]) ou[v] = 1, q.push(v);
	}
}

离散化优化

在 P1073 这道题目中，这一复杂度已经是最优的了，然而价格的大小实际上对输入开销没有影响。因此在该情景下，价格可以达到很大，此时 $\mathrm O(N+K)$ 的复杂度就显得不那么优了，我们可能需要一个复杂度只和 $N$ 相关的算法。

不妨将 $K$ 的范围扩大到 $1 \le K \le 10^9$（其实还可以扩大到更大，不过没什么必要）。

此时枚举 $K$ 种价格会超时，但是我们实际上只有 $N$ 个节点，也就是最多只有 $N$ 种存在的颜色，因此我们可以将价格离散化，或者将节点按照价格降序排序并枚举，这里提供前一种写法，只需要在主函数略微改动即可：

...
set<int> P;
...
int main() {
    ...
	for(int u = 1; u <= n; u++) cin >> p[u], P.insert(p[u]);
    ...
	for(int k : P) bfs_k(k);
    ...
}

奇技淫巧

注意到三个 BFS 函数的结构极为相似，我们实际上可以通过 lambda 表达式的方式进行复用，这里以朴素写法为例：

...
void bfs(vector<int> (&M)[N], int (&st)[N], function<bool(int)> push, function<void(int)> op) {
	queue<int> q;
	for(int u = 1; u <= n; u++) if(push(u)) st[u] = 1, q.push(u);
	while(q.size()) {
		int u = q.front();
		q.pop();
		op(u);
		for(int v : M[u]) if(!st[v]) st[v] = 1, q.push(v);
	}
}
int main() {
    ...
	bfs(H, un, [](int u){ return u == n; }, [](int _){});
	for(int k = 1; k < K; k++) bfs(H, ukn[k], [&k](int u){ return un[u] && p[u] == k; }, [](int _){});
	bfs(G, ou, [](int u){ return u == 1; }, [](int u){
		for(int k = K - 1; k; k--)
			if(ukn[k][u]) { ans = max(ans, k - p[u]); return; }
	});
    ...
}

关于分层图解法

在 Luogu 该题的题解区中，有很多选手使用了分层图来解决这道题目。问题在于，这道题的设计（一次买入一次卖出）使得图中必然有负权边，因此只能够使用能够处理负权边的 SPFA 来解决这个问题。

令我惊奇的是，在这道题中 SPFA 并没有被卡掉，仔细思考一下可以发现，SPFA 的时间复杂度不会来到 $\mathrm O(MN)$ 的原因还是本题中 $K$ 极小的范围。这张图上的路径长度在区间 $(-K, K)$，因此每个节点被更新的次数一定小于 $2K$，因而 SPFA 解法的复杂度实际上是 $\mathrm O(NK)$。