發表新討論
#39580: 分層圖最短路


qerpzzea@gmail.com (賽希爾 cecill(陳宥穎))

學校 : 高雄市立中正高級中學
編號 : 169400
來源 : [163.32.60.236]
最後登入時間 ：
2024-11-06 12:35:37
d779. NOIP2009 3.最优贸易 -- NOIP2009提高组第三题 | From: [114.40.45.175] | 發表日期 : 2024-03-08 12:27

求1號點到n號點的 B點買入,A點賣出的最大收益   A(最大值)-B(最小值)

方法

1.建3層圖 
設1號點的價格為x 
第一層->第二層 為買入 ex: 1-->1+n 邊權為 -x
第二層->第三層 為賣出 ex: 1+n-->1+2*n 邊權為 +x
各層內邊權為0 表示連通
最後答案在第三層,也就是 1->3*n的最短路

 
#39581: Re: 分層圖最短路


qerpzzea@gmail.com (賽希爾 cecill(陳宥穎))

學校 : 高雄市立中正高級中學
編號 : 169400
來源 : [163.32.60.236]
最後登入時間 ：
2024-11-06 12:35:37
d779. NOIP2009 3.最优贸易 -- NOIP2009提高组第三题 | From: [114.40.45.175] | 發表日期 : 2024-03-08 12:31

求1號點到n號點的 B點買入,A點賣出的最大收益   A(最大值)-B(最小值)

方法

1.建3層圖 
設1號點的價格為x 
第一層->第二層 為買入 ex: 1-->1+n 邊權為 -x
第二層->第三層 為賣出 ex: 1+n-->1+2*n 邊權為 +x
各層內邊權為0 表示連通
最後答案在第三層,也就是 1->3*n的最短路

更正 :

"最後答案在第三層,也就是 1->3*n的最短路"

由於是求最大值,所以求的是最長路

 
ZeroJudge Forum