[Wikioi 1173][NOIP 2009提高组]最优贸易(疑难题)

题目描述 Description

【问题描述】
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 条道路的信息（每条道路所连接的两个城市的编号
以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

输入描述 Input Description

第一行包含 2 个正整数n 和m，中间用一个空格隔开，分别表示城市的数目和道路的
数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n 个城
市的商品价格。
接下来 m 行，每行有3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，
表示这条道路是城市x 到城市y 之间的单向道路；如果z=2，表示这条道路为城市x 和城市
y 之间的双向道路。

输出描述 Output Description

包含1 个整数，表示最多能赚取的旅费。如果没有进行贸易，
则输出0。

样例输入 Sample Input

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

样例输出 Sample Output

5

妈的一直80分，调三四个小时才AC，蛋疼啊，卧草草草

用SPFA做，和其他题不同，这里不求最短路，而是路径上的结点最小值/最大值，最后起点到终点间的结点最大值减去最小值就是结果

#include 
#include 
#define MAXN 100001
#define INF 10000000
struct LINE //保存边的结构体 
{int from; //边的起点 int to; //边的终点 int Last; //上一条边的编号 int Next; //下一条边的编号 
}ln[MAXN*10];
int nLine=0,n,m; //nLine记录边的个数 
int price[MAXN]; //price[i]=第i个点的价格 
int maxSold[MAXN]; //sold[i]=到达点i的最大卖出价
int minBuy[MAXN]; //minBuy[i]=到达点i的最小买入价
int que[MAXN*10]; //数组que保存队列 
int visit[MAXN*10]; //visit[i]=1表示第i个点已经访问过了，visit[i]=0表示第i个点没访问过
int lastLine[MAXN]; //lastLine[i]=以i为终点的边的编号
int nextLine[MAXN]; //nextLine[i]=以i为起点的边的编号
int min(int a,int b)
{if(ab) return a;return b;
}
void insert(int u,int v) //建立边u->v
{nLine++;ln[nLine].from=u;ln[nLine].to=v;ln[nLine].Last=lastLine[u];ln[nLine].Next=nextLine[v]; lastLine[u]=nLine;nextLine[v]=nLine;
} 
void SPFA1() //第一次SPFA,从起点到终点找出到达点i时的，路途上的最小买入价
{int head=0,tail=0; //初始时，队列的队首、队尾均为0que[0]=1;minBuy[1]=price[1];visit[1]=1;//初始时，队列的队首为第1个点(队首位于0),到达第1个点时的最小买入价为第1个点的价格,标记第1个点访问过while(head<=tail) //队列不为空{int p=lastLine[que[head]]; //p=队首点对应编号while(p>0){if(minBuy[ln[p].to]>minBuy[que[head]]||price[ln[p].to]0) //由队首点为终点的边开始，搜索完所有联通的点{if(maxSold[ln[p].from]maxSold[ln[p].from]) //松弛获得更优解{maxSold[ln[p].from]=max(maxSold[que[head]],price[ln[p].from]);if(!visit[ln[p].from]) que[++tail]=ln[p].from; //如果没有访问过，将更优解入队visit[ln[p].from]=1; //标记该点已经访问过}p=ln[p].Next; //开始访问与该边连接的上一边}visit[que[head]]=0;head++; //队首的点处理完成，队首出队}
} 
int main()
{int i,j,x,y,z,ans=0;memset(minBuy,127,sizeof(minBuy));scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&price[i]);for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);insert(x,y); //建立边x->yif(z==2)insert(y,x); //如果是无向边，再建立边y->x}SPFA1();SPFA2();for(i=1;i<=n;i++)ans=max(maxSold[i]-minBuy[i],ans);printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！