最優貿易

題目描述

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 之間的雙向道路。

輸出描述

包含1 個整數，表示最多能賺取的旅費。如果沒有進行貿易，
則輸出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≤x，y≤n，1≤z≤2，1≤各城市
水晶球價格≤100。

解析

對于每個點，求出到達該點得到的最小價格和該點到n的最大價格，在每個點最大值和最小值之差中找最大值就得到答案了；

?

#include<cstdio> #include<queue> #include<cstring> using namespace std; struct node{int to,next; }q[1000002],p[1000002]; int n,m,head[100002]={0},head2[100002]={0},low[100002],ma[100002]; int a[100002],x,y,z,cnt,ans; int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a>b?b:a;} int add(int x,int y){ //邊表； cnt++;q[cnt].to=y; //第cnt條邊所指向的點； q[cnt].next=head[x]; //指向與第cnt條邊有共同起點、上一次讀入的邊； head[x]=cnt; //指向x最后讀入的一第條邊； p[cnt].to=x; /*反向存邊*/ p[cnt].next=head2[y];head2[y]=cnt; } void spfa(){queue<int> d;d.push(1);memset(low,0x7f,sizeof(low));low[1]=a[1];while(!d.empty()){int t=d.front();d.pop();for(int i=head[t];i;i=q[i].next){ //統計從1到達與t相連的點now時的最小值； int now=q[i].to;if(low[now]>min(a[now],low[t]))low[now]=min(a[now],low[t]),d.push(now);}} } void spfa2(){queue<int> d;d.push(n);memset(ma,0,sizeof(ma));ma[n]=a[n];while(!d.empty()){int t=d.front();d.pop();for(int i=head2[t];i;i=p[i].next){ //統計從n到達與t相連的點now時的最大值； int now=p[i].to;if(ma[now]<max(a[now],ma[t])){ma[now]=max(a[now],ma[t]);d.push(now);}}} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y);if(z==2) add(y,x);}spfa();spfa2();for(int i=1;i<=n;i++) ans=max(ans,ma[i]-low[i]);printf("%d\n",ans);return 0; } View Code

?

?

?

轉載于:https://www.cnblogs.com/qingang/p/5717011.html

總結

以上是生活随笔為你收集整理的2009 最优贸易的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。