Luogu P4772 灰化肥,会挥发 题解

Description

在Farmer Justin的农场中有许多灰化肥,它们都堆积在A仓库里。为了方便施肥,Farmer Justin需要修一些公路使得他能用拖拉机把这些灰化肥拉到其他仓库里。由于Farmer Justin及其懒惰,所以他只想一次拉完所有的灰化肥送到其他仓库里。但是灰化肥见光易挥发,所以Farmer Justin需要尽快把这些灰化肥拉完。现在告诉你Farmer Justin农场的构成地图,请你帮帮他计划一条从A仓库出发走完所有仓库的方案吧!由于Farmer Justin非常的讨厌浪费时间,所以你只需要告诉他最短的距离和走过所有农场的顺序。(注意:拖拉机走的时候是四联通的。)

Solution

状压DP+BFS

首先先暴力BFS跑出任意两个点之间的距离。

然后考虑DP,设$dp[i][j]$表示当前已经遍历过的点状态为$i$,最后一个遍历的点为$j$的最小值。

很明显:

$$dp[i][j]=dp[i\oplus (1<<k-1)][k]+cost[k][j](i\&(1<<k-1)!=0)$$

又因为要记录路径,于是开一个数组$g$与$dp$类似,更新的过程中记录下路径即可。

注意要开long long。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇