题解 洛谷 Luogu P1073 [NOIP 2009 提高组] 最优贸易 强连通分量 Tarjan 缩点 拓扑排序 动态规划 C++

题目

传送门

P1073 [NOIP 2009 提高组] 最优贸易 - 洛谷https://www.luogu.com.cn/problem/P1073

思路

以下将强连通分量简称为 SCC

有两个目标

目标一：至多买入一次卖出一次，使收益最大 (不会低于 0)

目标二：以 1 为起点，以 n 为终点 (保证从 1 可达 n)

我们只能先买入再卖出，为了完成目标一，我们显然需要知道最低买入价、最高卖出价

即，以某个节点 x 为中点时，x 及其之前的最低价、x 及其之后的最高价
这些信息可以通过 DP 得到

且需要正向建图 DP (得到 x 及其之前的最低价)、反向建图 DP (得到 x 及其之后的最高价)

共计两轮 DP

无特殊性质的有向图不便于 DP，我们可以考虑缩点

缩点后，只要知道每个 SCC 中的最低价和最高价 (将此视为新图的点权) 即可求解

因此缩点是可行的

缩点后无特殊性质的有向图变为 DAG，此后即可方便地 DP (拓扑排序 DP)

为了完成目标二，我们需要在拓扑排序 DP 前取出非法节点。非法节点即不能对答案有贡献的节点

举个例子，对于有向图 (1, 4), (2, 4), (3, 2)，正向拓扑排序 DP 时，2, 3 都是非法节点

因为起点只有 1，2, 3 都不是起点，且 1 不会到达 2, 3，它们不能对答案有贡献，不然就错了

为什么要取出非法节点呢？因为拓扑排序 DP 需要正确地维护入度

若有非法节点通向合法节点，则这些合法节点的入度会永久增加而始终无法入队

那怎么取出非法节点呢？还是用拓扑排序

不会的先去学习一下 <Luogu.P1807 最长路> 比较好，取出非法节点这一步和本题是一样的

P1807 最长路 - 洛谷https://www.luogu.com.cn/problem/P1807之后遍历所有 SCC 即可，如果在合法分支上，更新 ans：ans = max(ans, dp[1][i] - dp[0][i])

总结

1.输入，缩点

2.建新图 (正向 & 反向)

3.拓扑排序剥离非目标分支，拓扑排序 DP (正向 & 反向)

4.遍历 scc，根据 DP 信息计算答案

细节

1.正向新图和反向新图的信息可用下标控制，实现代码复用

正向新图用下标 0，DP 最低价；反向新图用下标 1，DP 最高价

2.缩点时 Tarjan(1) 即可，1 不可达的节点就不用管了

3.原图存一个正向的即可，有这个信息，在建新图时就可以建反向的

其余细节见代码注释

代码

#include <functional>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
//V 用于为 DP 赋初值，最低价赋初值为 0x3f，最高价赋初值为 0
constexpr int N = 1E5 + 5, V[2]{ 0x3f, 0 };
//原图、新图 (正向 & 反向)
vector<int> to[N], scc_to[2][N];
//Tarjan 缩点要用的、SCC 点权 (最低价 & 最高价)、原图点权、新图入度 (正向 & 反向) DP 信息 (最低价 & 最高价)、合法分支的起点 (正向 & 反向)、拓扑排序要用的队列
int dfn[N], low[N], stk[N], scc_id[N], scc_w[2][N], w[N], scc_from[2][N], dp[2][N], start[2], que[N];
//Tajjan 缩点要用的、是否在非法分支上
bool instk[N], invalid[N];
//Tarjan 缩点要用的、输入要用的、答案
int time_, top = -1, scc_cnt, n, m, a, b, c, ans;
//通过下标控制最小值最大值
int A(int x, int y) { return min(x, y); }
int B(int x, int y) { return max(x, y); }
function<int(int, int)> op[2]{ A, B };
void Tarjan(int x)
{dfn[x] = low[x] = ++time_;stk[++top] = x;instk[x] = true;for (auto X : to[x])if (dfn[X] == 0)Tarjan(X),low[x] = min(low[x], low[X]);else if (instk[X])low[x] = min(low[x], dfn[X]);if (low[x] == dfn[x]){int X;++scc_cnt;scc_w[0][scc_cnt] = 1E9; //SCC 最低价初始化为 INF，SCC 最高价初始化为 0do{X = stk[top--];instk[X] = false;scc_id[X] = scc_cnt;scc_w[0][scc_cnt] = op[0](scc_w[0][scc_cnt], w[X]); //更新 SCC 点权scc_w[1][scc_cnt] = op[1](scc_w[1][scc_cnt], w[X]);} while (X != x);}
}
void preprocess() //输入，缩点
{cin >> n >> m;for (int i = 1; i <= n; ++i) //原图点权cin >> w[i];while (m-- && cin >> a >> b >> c)if (c == 1)to[a].emplace_back(b);elseto[a].emplace_back(b),to[b].emplace_back(a);Tarjan(1);start[0] = scc_id[1]; //新图正向拓扑排序时，合法分支起点是原图 1 所在的 SCCstart[1] = scc_id[n]; //新图反向拓扑排序时，合法分支起点是原图 n 所在的 SCC
}
void build() //建新图 (正向 & 反向)
{for (int i = 1; i <= n; ++i){int x = scc_id[i];for (auto j : to[i]){int y = scc_id[j];if (x == y) continue;scc_to[0][x].emplace_back(y);++scc_from[0][y];scc_to[1][y].emplace_back(x);++scc_from[1][x];}}
}
void toposort(int flag) //拓扑排序剥离非目标分支，拓扑排序 DP (正向 & 反向)
{//常用数组降维，简化代码auto& scc_to_ = scc_to[flag];auto& scc_w_ = scc_w[flag];auto& scc_from_ = scc_from[flag];auto& dp_ = dp[flag];auto& op_ = op[flag];auto& start_ = start[flag];//剥离非法分支int head = 0, tail = -1;for (int i = 1; i <= scc_cnt; ++i)if (i != start_ && scc_from_[i] == 0)que[++tail] = i;while (head <= tail){int x = que[head++];invalid[x] = true;for (auto X : scc_to_[x])if (X != start_ && --scc_from_[X] == 0)que[++tail] = X;}//拓扑排序 DPmemset(dp_, V[flag], sizeof(dp_[0]) * (scc_cnt + 1)); //别忘了为 DP 信息赋初值que[++tail] = start_;while (head <= tail){int x = que[head++];dp_[x] = op_(dp_[x], scc_w_[x]);for (auto X : scc_to_[x]){dp_[X] = op_(dp_[X], dp_[x]);if (--scc_from_[X] == 0)que[++tail] = X;}}
}
void solve() //遍历 scc，根据 DP 信息计算答案
{for (int i = 1; i <= scc_cnt; ++i)if (invalid[i] == false) //在合法分支上ans = max(ans, dp[1][i] - dp[0][i]);cout << ans;
}
int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);preprocess();build();toposort(0);toposort(1);solve();return 0;
}