P1073 [NOIP2009 提高组] 最优贸易 题解
ctzm
·
·
题解
前言：经历了这个帖子和这个帖子两次 hack 后，题解区就只剩下分层图最长路了，唯一的 Tarjan 也被 hack 掉，只是保存下来而已。
原本我加在自己的练习题单，准备当成分层图做，结果学校学 Tarjan 时又有这个题……那就两种都写一遍吧。
分层图写得很顺利，很快就过了，但看大家的提交记录，好家伙，全在分层图，并且最长路写 dij 的居然都能过，真的不怕最长路被卡到 WA/TLE 吗？？？
很少一部分人依然坚持写 Tarjan，但是基本也被后来加的数据 hack 了，作为一个 SPFA 被卡怕的人，我决定写一篇 Tarjan 题解，以让 Tarjan 党能够使用最喜欢的稳定线性做法通过本题，而不是某个已经【【】】的东西。
题意简述
一个商人在有向图上从 1 走到 n，点 i 处买和卖货物的价格都是 w_i，商人至多只能买和卖商品一次，问最多盈利多少。
## Solution
缩点题目的一般套路：在 DAG（有向无环图）上非常好做（往往是拓扑序上 DP）+ 一个强连通分量可以经过一定处理变成一个点，并且答案不受影响。
看到部分分的描述：“不存在一条旅游路线，可以从一个城市出发，再回到这个城市。”
这句话本质上就是在说：“这个图是个 DAG（有向无环图）。”
记 $f_i$ 为“从 $1$ 到 $i$ 的所有路径中，经过的点的货物价格的最小值”，假设我们在点 $v$ 卖出货物，那么最大利润就是 $w_v - f_v$。正确性是显然的：卖出价一定，想让利润变大，就得降低成本，贪心地选择可能经过的最小的成本就好了。
如何求 $f_i$？首先，边界情况 $f_1$ 一定为 $w_1$，然后对于 DAG 上的每条边 $(u,v)$，有 $f_v = \min(f_v,\min(f_u,w_v))$，转移按拓扑序枚举点连接的边就好了，没有后效性的。
考虑并不是 DAG，也就是有环的情况：用 Tarjan 缩点，此处不细讲 Tarjan 算法，顺便记录每个强连通分量里所有点的 $w_i$ 最大值和最小值，记为 $maxw$ 和 $minw$。
缩完点重新建边后，对于每条边 $(u,v)$，转移式变为 $f_v = \min(f_v,\min(f_u,minw_v))$，统计答案方法就变为 $maxw_i - f_i$，正确性留给大家自行思考。
注意，这道题有坑！统计答案时（假设枚举到点 $i$ 作为卖出点），必须满足从 $1$ 可达 $i$，也从 $i$ 可达 $n$ 才能计入答案。
如何判断这两个条件？第一个条件可以偷懒，只对节点 $1$ 跑一遍 Tarjan。Tarjan 的本质其实还是深搜，只是在上面记录信息以缩点，如果 $1$ 到达不了某个点， Tarjan 也不会找到它，忽略掉就好。
第二个条件有点难处理，毕竟你不可能每个点都深搜一遍吧。一个简单易想易写的方案是，对缩点后产生的 DAG 建反图，然后从点 $n$ 所在的 SCC 跑深搜，被访问到了就是满足这个条件的。
有些题目也会考到这种“单汇”的最短路或者可达性之类的东西，通常的最短路 / 搜索都是“单源”的，只需要建个反图就能转化为“单汇”。
### code
```cpp
int n,m,cnt,scc,a[100010],dp[100010],dfn[100010],low[100010],col[100010],miw[100010],maw[100010];
vector<int> v[100010],V[100010],v_[100010];
stack<int> s;
bool vis[100010];
/*
cnt为tarjan的时间戳，scc为scc个数
a为价格，col表示每个点属于哪个scc
miw/maw表示每个scc内的最小/最大价格
v/V/v_表示原图/缩点后图/缩点后反图
s为tarjan的栈，vis是dfs中的访问标记
*/
void tarjan(int x){
dfn[x]=low[x]=++cnt;
s.push(x);
for(int i:v[x]){
if(!dfn[i]){
tarjan(i);
low[x]=min(low[x],low[i]);
}
else if (!col[i]){
low[x]=min(low[x],dfn[i]);
}
}
if(low[x]==dfn[x]){
scc++;
miw[scc]=1e9;//初始化
maw[scc]=-1;
while(1){
int tmp=s.top();
col[tmp]=scc;
miw[scc]=min(miw[scc],a[tmp]);//记录最小值和最大值
maw[scc]=max(maw[scc],a[tmp]);
s.pop();
if(tmp==x)break;
}
}
}
void dfs(int x){
vis[x]=1;
for(int i:v_[x])if(!vis[i])dfs(i);
}
void solve(){
int ans=0;
memset(dp,0x3f,sizeof dp);
dp[col[1]]=miw[col[1]];
for(int _=scc;_>=1;_--){//tarjan 保证了逆序枚举是一种合法的拓扑序，当然你想写正常拓扑也行
for(int i:V[_]){
dp[i]=min(dp[i],min(dp[_],miw[i]));//DAG dp 核心转移
}
}
for(int i=1;i<=scc;i++)if(vis[i])ans=max(ans,maw[i]-dp[i]);//统计答案注意是否可达n
cout<<ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int u,V_,t;
cin>>u>>V_>>t;
v[u].push_back(V_);
if(t==2)v[V_].push_back(u);//注意双向边
}
tarjan(1);
for(int i=1;i<=n;i++){
for(int j:v[i]){
if(col[i]!=col[j]&&col[i]&&col[j]){//注意，我们没跑完 整个图，意味着有些点的col为0，不应该加入，所以要特判
V[col[i]].push_back(col[j]);
v_[col[j]].push_back(col[i]);
}
}
}
dfs(col[n]);//如果 col[n] == 0 其实没有影响 上面的特判保证了点 0 不会向任何点连边
solve();
return 0;
}
```
[AC 记录](https://www.luogu.com.cn/record/200076626)，不过感觉 tarjan 写这题坑点挺多，目前能通过所有 hack 数据，不过感觉不久也会被 hack 掉……就这样吧。