题目:
题目传送门
C国有n个大城市和m 条道路，每条道路连接这 n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1条。
C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n，阿龙决定从 1号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C国有 5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1~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 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入格式
第一行包含 2 个正整数n和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有3个正整数x,y,z每两个整数之间用一个空格隔开。如果 z=1,表示这条道路是城市x到城市y之间的单向道路；如果z=2,表示这条道路为城市 x和城市y之间的双向道路。
输出格式
一 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。
样例输入
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
样例输出
5
数据范围:
输入数据保证 1号城市可以到达n号城市。
对于 10%的数据，1≤n≤6。
对于 30%的数据，1≤n≤100。
对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于 100%的数据，1≤n≤100000,1≤m≤500000
题意分析:
首先这道题给出一个有向图,结点代表各个城市,结点蕴含权值也就是水晶球价格,代表着各个城市的水晶球价格不同,我们必须从1号结点出发,最终到达n号结点,在旅行途中我们将水晶球买入,并且选入合适的城市卖出。(注意,也可以先到达n号城市,返回其他城市卖掉水晶球,在返回n号城市结束旅行)
解题思路:
这张图的边没有权值,权值在结点上,我们遍历整个图需要找到权值最大的值,以及权值最小的值,我们并不关心权值最大/最小值在哪个点,也就是我们需要遍历整个图找到最大权值和最小权值,并且要保证他们是连通的,必须在一条路径上,保证相互能够到达。最后我们遍历每个点,用每个点的最大值和最小值做差,通过ans记录取max得出差值最大的值。
那么如何找到最大权值和最小权值,并且保证连通呢?
我们可以利用spfa求出从1号结点到任意结点x的最小值,只要我们把松弛操作由d[u]+edge[i].v<d[v]改为d[u]<d[v],只要满足d[u]<d[v]那么d[v]就更新为d[u],通过spfa对所有点进行这样的松弛操作,那么我们可以得出从1号结点出发到任意结点连通路径上的最小值。
图示1-1（SPFA更新最小值的过程）
通过上图我们可以看到从1号结点出发经过spfa得到权值最小的值为1.
那么如何得到最大值呢??
通过上述思路有的同学就会想到在从1号结点出发经过spfa,将松弛操作改为d[u]>d[v]就更新d[v]=d[u] 这样行不行?
答案:不行的!
为什么呢?
因为无法保证最小值和最大值与n点连通,也就是在最小值的地方买入,在最大值的地方卖出但无法到达n点所以不满足题意。
图示1-2(为什么不能从1号结点开始找出最大值)
如何解决?
我们利用反向图,明确一个概念,正向图能连通的点,在反向图中也能够连通!我们将正向图的边的方向全部取反,然后以n为起点,经过spfa更新n到x得出每条路径上的最大值,这样就可以保证在最大值点卖出,并且能够到达n点。
图示1-3(反向图找出路径最大值)我们利用图1-1的结点和权值
(注意这是反向图哦~)
我们最后再来一个完结版本
代码实现:
我们采用链式前向星存两个图,一个正向图,一个反向图
用两个数组Min[i],Max[i]存放到i号结点的最大最小值。(要注意这两个数组的初始化)
用w数组存放第i号结点的权值
写出从1号出发正向的spfa_1,和从n号出发反向的spfa_2
spfa算法不懂看这里。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct edge_1{
int to,next;//下一个结点to,nex下一条边
}edge_1[maxn];
struct edge_2{
int to,next;
}edge_2[maxn];
int vis[maxn],w[maxn],Min[maxn],Max[maxn],head_1[maxn],head_2[maxn];
int n,m,sum_1,sum_2;
void add_1(int u,int v)
{
edge_1[++sum_1].to=v;
edge_1[sum_1].next=head_1[u];
head_1[u]=sum_1;
}
void add_2(int u,int v)
{
edge_2[++sum_2].to=v;
edge_2[sum_2].next=head_2[u];
head_2[u]=sum_2;
}
void spfa_1(int start)
{
memset(vis,0,sizeof(vis));
memset(Min,0x7f7f7f7f,sizeof(Min));//初始化最大
queue<int> q;
q.push(start);
Min[start]=w[start];
vis[start]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;//出队取消标记
for(int i=head_1[u];i;i=edge_1[i].next)
{
int v=edge_1[i].to;
if(Min[v]>min(Min[u],w[v]))
{
//更新v点的最小值
Min[v]=min(Min[u],w[v]);
if(!vis[v])
{
q.push(v);
vis[v]=1;//入队标记
}
}
}
}
}
void spfa_2(int last)
{
memset(vis,0,sizeof(vis));
memset(Max,-0x7f7f7f7f,sizeof(Max));
queue<int> q;
q.push(last);
Max[last]=w[last];
vis[last]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head_2[u];i;i=edge_2[i].next)
{
int v=edge_2[i].to;
if(Max[v]<max(Max[u],w[v]))
{
Max[v]=max(Max[u],w[v]);
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
//读入每个点的权值
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
//添加边
for(int i=1;i<=m;i++)
{
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
add_1(u,v);//正向图
add_2(v,u);//反向图
if(k==2)
{
add_1(v,u);//正向图
add_2(u,v);//反向图
}
}
spfa_1(1);
spfa_2(n);
int ans=-0x7f7f7f7f;//无穷小数
for(int i=1;i<=n;i++)
{
ans=max(ans,Max[i]-Min[i]);//求最小
}
printf("%d\n",ans);
return 0;
}
多多点赞支持~~~
