题目描述
C国有n个大城市和m 条道路，每条道路连接这 n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1条。
C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C国 n 个城市的标号从 1~ n，阿龙决定从 1号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C国有 5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1 n1~n1 n 号城市的水晶球价格分别为 4,3,5,6,1
阿龙可以选择如下一条线路：1->2->3->5，并在 2号城市以3 的价格买入水晶球，在 3号城市以5的价格卖出水晶球，赚取的旅费数为 2。
阿龙也可以选择如下一条线路1->4->5->4->5，并在第1次到达5号城市时以 1的价格买入水晶球，在第 2次到达4 号城市时以6的价格卖出水晶球，赚取的旅费数为5。
现在给出 n个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
思路：
这道题很简单，就是让我们找一个最小买入点和一个最大卖出点
首先，我们要缩一下点（其实不缩也可以），建一张新图
然后，我们从1点开始，跑一遍用点权更新的spfa（可以求出每个点之前的最小买入值）
然后，我们建一张反图，从m开始跑一个用点权更新的spfa，求出一个点之后卖出的最大值
对于每个新点，如果差价大于答案，就更新答案即可
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define rij register int j
#define rii register int i
using namespace std;
int low[],dfn[],top,sta[],bnt;
int n,m,head[],last[],dq[];
int sum[],color[],tot,vis[];
int maxn[],minx[],dp[],cnt;
int maxx[],mixx[],pd[];
struct cb{
int from,to,p;
}y[];
struct ljb{
int to,nxt,from;
}x[];
queue<int> q;
void add(int from,int to)
{
bnt++;
x[bnt].to=to;
x[bnt].from=from;
if(head[from]==)
{
head[from]=bnt;
}
else
{
x[last[from]].nxt=bnt;
}
last[from]=bnt;
}
void tarjan(int wz)
{
top++;
sta[top]=wz;
vis[wz]=;
cnt++;
dfn[wz]=cnt;
low[wz]=cnt;
for(rii=head[wz];i!=;i=x[i].nxt)
{
int ltt=x[i].to;
if(dfn[ltt]==)
{
tarjan(ltt);
low[wz]=min(low[wz],low[ltt]);
}
else
{
if(vis[ltt]==)
{
low[wz]=min(low[wz],dfn[ltt]);
}
}
}
if(dfn[wz]==low[wz])
{
tot++;
while(sta[top+]!=wz)
{
color[sta[top]]=tot;
vis[sta[top]]=;
maxn[tot]=max(maxn[tot],dq[sta[top]]);
minx[tot]=min(minx[tot],dq[sta[top]]);
top--;
}
}
}
void spfa(int wz)
{
pd[wz]=;
mixx[wz]=minx[wz];
for(rii=head[wz];i!=;i=x[i].nxt)
{
q.push(i);
}
while(q.empty()==false)
{
int ltt=q.front();
q.pop();
int to=x[ltt].to;
int from=x[ltt].from;
pd[from]=;
mixx[to]=min(mixx[to],minx[to]);
if(mixx[to]>mixx[from])
{
mixx[to]=mixx[from];
for(rii=head[to];i!=;i=x[i].nxt)
{
q.push(i);
}
}
if(pd[to]==)
{
for(rii=head[to];i!=;i=x[i].nxt)
{
q.push(i);
}
}
}
}
void spaf(int wz)
{
maxx[wz]=maxn[wz];
for(rii=head[wz];i!=;i=x[i].nxt)
{
q.push(i);
}
while(q.empty()==false)
{
int ltt=q.front();
q.pop();
int to=x[ltt].to;
int from=x[ltt].from;
pd[from]=;
maxx[to]=max(maxx[to],maxn[to]);
if(maxx[to]<maxx[from])
{
maxx[to]=maxx[from];
for(rii=head[to];i!=;i=x[i].nxt)
{
q.push(i);
}
}
if(pd[to]==)
{
for(rii=head[to];i!=;i=x[i].nxt)
{
q.push(i);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(rii=;i<=n;i++)
{
minx[i]=;
mixx[i]=;
}
for(rii=;i<=n;i++)
{
scanf("%d",&dq[i]);
}
for(rii=;i<=m;i++)
{
int from,to,p;
scanf("%d%d%d",&from,&to,&p);
y[i].from=from;
y[i].to=to;
y[i].p=p;
if(p==)
{
add(to,from);
}
add(from,to);
}
for(rii=;i<=n;i++)
{
if(dfn[i]==)
{
tarjan(i);
}
}
memset(head,,sizeof(head));
memset(last,,sizeof(last));
memset(x,,sizeof(x));
for(rii=;i<=m;i++)
{
int from=y[i].from;
int to=y[i].to;
int p=y[i].p;
if(color[from]!=color[to])
{
if(p==)
{
add(color[to],color[from]);
}
add(color[from],color[to]);
}
}
spfa(color[]);
memset(head,,sizeof(head));
memset(last,,sizeof(last));
memset(x,,sizeof(x));
memset(pd,,sizeof(pd));
for(rii=;i<=m;i++)
{
int from=y[i].from;
int to=y[i].to;
int p=y[i].p;
if(color[from]!=color[to])
{
if(p==)
{
add(color[from],color[to]);
}
add(color[to],color[from]);
}
}
spaf(color[n]);
int ans=;
while(q.empty()==false)
{
q.pop();
}
for(rii=;i<=n;i++)
{
ans=max(maxx[i]-mixx[i],ans);
}
cout<<ans;
}