「NOIP2009」 最优贸易 - 最短路

本文主要是介绍「NOIP2009」 最优贸易 - 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

$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\le n\le 6$ 。
对于30%的数据， $1\le n\le 100$ 。
对于50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于100%的数据， $1\le n\le 100000，1\le m\le 500000，1\le x,y\le n，1\le z\le 2，1\le $各城市水晶球价格$\le 100$。

分析

本题数据比较水，对于每一种最多的情况只是在相邻两个城市之间贸易，所以以下程序能AC。

#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <cmath>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
struct Edge {int from,to,next;
}e[500005],ef[500005];
struct Bian {int from,to,weight;
}b[500005];
int h[100005],cnt,hf[100005],cntf,ans;
int n,m,cost[100005],t;
bool vis[100005];
int d[100005][2];
void addedge(int x,int y) {e[++cnt]=(Edge){x,y,h[x]};h[x]=cnt;
}
void addedgef(int x,int y) {ef[++cntf]=(Edge){x,y,hf[x]};hf[x]=cntf;
}
void spfa(int v0) {queue<int> q;q.push(v0);memset(vis,0,sizeof(vis));vis[v0]=1;memset(d,0x3f,sizeof(d));d[v0][1]=0;while (!q.empty()) {int w=q.front();q.pop();vis[w]=0;for (int i = h[w];i;i = e[i].next) {int v=e[i].to;if (d[v][1]>d[w][1]+1) {d[v][1]=d[w][1]+1;if (!vis[v]) {q.push(v);vis[v]=1;}}}}
}
void spfa2(int v0) {queue<int> q;q.push(v0);memset(vis,0,sizeof(vis));vis[v0]=1;d[v0][0]=0;while (!q.empty()) {int w=q.front();q.pop();vis[w]=0;for (int i = hf[w];i;i = ef[i].next) {int v=ef[i].to;if (d[v][0]>d[w][0]+1) {d[v][0]=d[w][0]+1;if (!vis[v]) {q.push(v);vis[v]=1;}}}}
}
bool cmp(Bian a,Bian b) {return a.weight>b.weight;
}
int main() {scanf("%d%d",&n,&m);for (int i = 1;i <= n;i++) scanf("%d",&cost[i]);for (int i = 1;i <= m;i++) {int a,bb,z;scanf("%d%d%d",&a,&bb,&z);addedge(a,bb);addedgef(bb,a);++t;b[t].from=a;b[t].to=bb;b[t].weight=cost[bb]-cost[a];if (z==2) {addedge(bb,a);addedgef(a,bb);++t;b[t].from=bb;b[t].to=a;b[t].weight=cost[a]-cost[bb];}}spfa(1);spfa2(n);sort(b+1,b+t+1,cmp);//下面这一坨就已经出错了，但还是能过。for (int i = 1;i <= t;i++) {if (d[b[i].from][0]!=0x3f3f3f3f&&d[b[i].to][1]!=0x3f3f3f3f) {ans=b[i].weight;break;}}printf("%d",max(ans,0));return 0;
}

正解应该是用两遍SPFA或用tarjan缩点后关键路径，这里讲讲两遍SPFA的思路。

买入的一个城市 $A$ 与卖出的城市 $B$ 一定在 $1-n$ 的一条路上，并且$A$一定在$B$ 的前面，这样才能卖出于$B$ 。用 $MIN[i]$ 表示$1-i$ 号城市中的最小的买入价格的城市，用 $MAX[i[$ 表示从 $n-i$ 号城市中最大的卖出价格的城市，这样， A n s = max ⁡ 1 ≤ i ≤ n { M A X [ i ] − M I N [ i ] } Ans=\max\limits_{1\le i\le n} \{MAX[i]-MIN[i]\} Ans=1≤i≤nmax​{MAX[i]−MIN[i]} 。至于求 $MAX[i],MIN[i]$ ，可以用SPFA或DFS或BFS。从 $n$ 跑的时候要用到反图，所以要先建反图。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <cmath>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
struct Edge {int to,next;
}e[500005],ef[500005];
int h[100005],cnt,hf[100005],cntf,ans;
int n,m,cost[100005];
bool vis[100005];
int mx[100005],mn[100005];
void addedge(int x,int y) {e[++cnt]=(Edge){y,h[x]};h[x]=cnt;
}
void addedgef(int x,int y) {ef[++cntf]=(Edge){y,hf[x]};hf[x]=cntf;
}
void spfa(int v0) {queue<int> q;q.push(v0);memset(vis,0,sizeof(vis));for (int i= 1;i <= n;i++) mn[i]=0x7fffffff;vis[v0]=1;mn[v0]=cost[v0];while (!q.empty()) {int w=q.front();q.pop();vis[w]=0;for (int i = h[w];i;i = e[i].next) {int v=e[i].to;if (mn[v]>min(mn[w],cost[v])) {mn[v]=min(mn[w],cost[v]);if (!vis[v]) {q.push(v);vis[v]=1;}}}}
}
void spfa2(int v0) {queue<int> q;q.push(v0);memset(vis,0,sizeof(vis));for (int i = 1;i <= n;i++) mx[i]=0;vis[v0]=1;mx[v0]=cost[v0];while (!q.empty()) {int w=q.front();q.pop();vis[w]=0;for (int i = hf[w];i;i = ef[i].next) {int v=ef[i].to;if (mx[v]<max(mx[w],cost[v])) {mx[v]=max(mx[w],cost[v]);if (!vis[v]) {q.push(v);vis[v]=1;}}}}
}
int main() {scanf("%d%d",&n,&m);for (int i = 1;i <= n;i++) scanf("%d",&cost[i]);for (int i = 1;i <= m;i++) {int a,bb,z;scanf("%d%d%d",&a,&bb,&z);addedge(a,bb);addedgef(bb,a);if (z==2) {addedge(bb,a);addedgef(a,bb);}}spfa(1);spfa2(n);for (int i = 1;i <= n;i++) ans=max(ans,mx[i]-mn[i]);printf("%d",ans);return 0;
}

这篇关于「NOIP2009」 最优贸易 - 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---