链接
https://www.acwing.com/problem/content/343/
题目
C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。
任意两个城市之间最多只有一条道路直接相连。
这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。
C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。
但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到C国旅游。
当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。
设C国 n 个城市的标号从 1~n，阿龙决定从1号城市出发，并最终在 n 号城市结束自己的旅行。
在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。
阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。
请你告诉阿龙，他最多能赚取多少旅费。
注意：本题数据有加强。
输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。
如果z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。
输出格式
一个整数，表示答案。
数据范围
1≤n≤100000,
1≤m≤500000,
1≤各城市水晶球价格≤100
输入样例：
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例：
5
思路
两种做法：
tarjan缩点+拓扑DP
将可以相互到达的强连通子图缩块，记录每个块内的最高和最低价格，对于块之间一定由单向边构成且无环。则对图做拓扑DP，记录每个块以及可以到达它的块的最低价格，通过枚举在每个块内卖出获得的最大价值更新答案。
拓扑DP的过程需要记录这个块是否可以由1点达到，如果1号点不能到达某个块，那么也不能在这个块内买入或卖出。
代码
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<stack>
using namespace std;
const int N=1e5+7,M=1e6+7,INF=0x3f3f3f3f;
int Stack[N], low[N],stackk[N], dfn[N], inStack[N], belong[N],h[N];
int now, cnt,tot,rt; // now:时间戳，cnt强连通的个数
struct edge{
int v,nex;
}edges[M],e[M];
int head[N],edge_cnt,top;
void addedge(int u,int v){
edges[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
stack<int> s;
map<int,map<int,int> >mmp;
int price[N],Min[N],Max[N],in[N],ans[N];
void init() {
now = cnt =tot =rt= 0;
memset(head,-1,sizeof head);
memset(h,-1,sizeof h);
memset(Min,0x3f,sizeof Min);
memset(Max,-0x3f,sizeof Max);
}
void tarjan(int x){
dfn[x]=low[x]=++now;
inStack[x]=1;stackk[++top]=x;
for(int i=head[x];i;i=edges[i].nex){
int v=edges[i].v;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(inStack[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
rt++;
Max[cnt]=-INF;Min[cnt]=INF;
int t;
do{
t=stackk[top--];
Max[rt]=max(Max[rt],price[t]);
Min[rt]=min(Min[rt],price[t]);
inStack[t]=0;
belong[t]=rt;
}while(x!=t);
}
}
void ad(int u,int v){
e[++tot]=(edge){v,h[u]};
h[u]=tot;
}
int reach[N];
int main(){
int n,m;
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&price[i]);
}
for(int i=1;i<=m;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==1){
addedge(x,y);
}
else {
addedge(x,y);
addedge(y,x);
}
}
for(int i=1;i<=n;++i){
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;++i){
int u=belong[i];
for(int j=head[i];~j;j=edges[j].nex){
int v=belong[edges[j].v];
if(u==v||mmp[u][v]) continue;
ad(u,v);
in[v]++;
mmp[u][v]=1;
}
}
queue<int> q;
reach[belong[1]]=1;
for(int i=1;i<=rt;++i){
if(in[i]==0) q.push(i);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=h[u];~i;i=e[i].nex){
int v=e[i].v;
if(reach[u]){
reach[v]=1;
ans[v]=max(ans[v],ans[u]);
Min[v]=min(Min[u],Min[v]);
ans[v]=max(ans[v],Max[v]-Min[v]);
}
in[v]--;
if(!in[v]) q.push(v);
}
}
cout<<ans[belong[n]];
return 0;
}
分层图
从1号点出发跑spfa，记录每个点以及可以到达他的点买入的最低价格。再从n号点跑反向边spfa，记录每个点以及可以到达他的点卖出的最高价格。最后枚举每个点更新答案。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=500010 ;
int mn[N],mx[N],price[N],inq[N];
int hs[N],ht[N],tot1,tot2;
struct eg{
int v,nex;
}es[M*2],et[M*2];
void ads(int u,int v){
es[++tot1]=(eg){v,hs[u]};
hs[u]=tot1;
}
void adt(int u,int v){
et[++tot2]=(eg){v,ht[u]};
ht[u]=tot2;
}
void spfa(int s,int d[],int type,int h[],eg e[] ){
queue<int> q;
memset(inq,0,sizeof inq);
q.push(s);inq[s]=1;
d[s]=price[s];
while(!q.empty()){
int u=q.front();q.pop();
inq[u]=0;
for(int i=h[u];~i;i=e[i].nex){
int v=e[i].v;
if((type==1&&d[v]>min(d[u],price[v]))||(type==2&&d[v]<max(price[v],d[u])) ){
if(type==1) d[v]=min(d[u],price[v]);
if(type==2) d[v]=max(price[v],d[u]);
if(!inq[v]){
inq[v]=1;
q.push(v);
}
}
}
}
}
int main(){
int n,m;
memset(hs,-1,sizeof hs);
memset(ht,-1,sizeof ht);
memset(mx,-0x3f,sizeof mx);
memset(mn,0x3f,sizeof mn);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>price[i];
while(m--){
int u,v,type;
cin>>u>>v>>type;
if(type==1){
ads(u,v);
adt(v,u);
}
else {
ads(u,v);
ads(v,u);
adt(v,u);
adt(u,v);
}
}
spfa(1,mn,1,hs,es);
spfa(n,mx,2,ht,et);
int res=0;
for(int i=1;i<=n;++i) {
res=max(res,mx[i]-mn[i]);
}
cout<<res<<endl;
return 0;
}