6101 最优贸易 0x60「图论」
例题描述
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 之间的双向道路。
输出格式
一个整数，表示答案。
样例输入
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≤x，y≤n，1≤z≤2，1≤各城市 水晶球价格≤100。
来源
CCF NOIP2009 Contest Hunter - 信息学自助比赛平台
解题思路
之所以记录本题，是由于本题用到了一种值得学习的思想。 本题目标是在1n的路径上找到两个点p和q，还要使得q-p的权值最大。我们可以把求p和求q分为两个步骤，因为我们想使得p尽量小而q尽量大，且1p和pq和qn是连通的。 于是我们可以通过将边存在邻接表中，通过dijkstra算法，求出数组d，其中d[x]表示从1~x路径中，节点权值最小的权值。我们只需要将最短路中“用d[x] + w[x,y]更新d[y]”改成“用min(d[x] , price[y])更新d[y]即可”。 我们可以通过建立一张反图（在原图基础上把所有边方向取反后得到的图），保存在另一张邻接表中。这时我们对反图用dijkstra，d2[x]表示从n出发到x最大的节点权值。 于是此时每个节点x新增两个值：d[x]和d2[x]，我们取d2[x] - d[x]最大的值作为答案即可。
代码示例：
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5+10;
const int M = 2*5e5+10;//有向图哦，边双倍存
int ver[M],Next[M],head[N];
int d[N],price[N];
//以下是反图用
int ver2[M],Next2[M],head2[N],d2[N];
int tot,n,m,tot2;
bool vis[N];
priority_queue< pair<int,int> > q,q2;
void addEdge(int x,int y){
ver[++tot] = y; //建立原图
Next[tot] = head[x],head[x] = tot;
ver2[++tot2] = x; //建立反图
Next2[tot2] = head2[y],head2[y] = tot2;
}
void dijkstra(int s){
memset(vis,false,sizeof vis);
memset(d,0x3f,sizeof d);
d[s] = price[s];
q.push(make_pair(d[s],s));
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(int i = head[x]; i;i = Next[i]){
int y = ver[i];
d[y] = min(d[x],price[y]);
q.push(make_pair(-d[y],y));
}
}
}
void dijkstra2(int s){
memset(vis,false,sizeof vis);
memset(d2,0,sizeof d2);
d2[s] = price[s];
q2.push(make_pair(d2[s],s));
while(q2.size()){
int x = q2.top().second;q2.pop();
if(vis[x]) continue;
vis[x] = true;
for(int i = head2[x]; i;i = Next2[i]){
int y = ver2[i];
d2[y] = max(d2[x],price[y]);
q2.push(make_pair(-d2[y],y));
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%d",price+i);
for(int i = 1,x,y,z;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
addEdge(x,y);
if(z == 2) addEdge(y,x);
}
dijkstra(1);
dijkstra2(n);
int ans = 0;
for(int i = 1;i <= n;i++) ans = max(d2[i]-d[i],ans);
printf("%d\n",ans);
return 0;
}
参考书目
《算法竞赛进阶指南》,李煜东,P329.
