這道題可以說是CEOI歷史上最好的題目了
題目圖的限制很多 這就使得題目有一個(gè)很巧妙的解法
限制如下

所有的大廳和通道都在同一水平面上。

沒有兩條通道相交。

有一些大廳位于山洞的外圈上，我們稱其為外廳。

其他所有位于外圈內(nèi)部的大廳被稱為是內(nèi)廳。

有且僅有一個(gè)外廳有著一個(gè)通向山洞的入口。

每一個(gè)大廳都恰好連接著三條通道，通向三個(gè)不同的另外的大廳。對(duì)于任意一個(gè)外廳，則有兩條通道通向外圈上另外兩個(gè)鄰接者的外廳，另一條通道連接著一個(gè)內(nèi)廳。

連接外廳的通道稱作外通道，其他的稱作內(nèi)通道。

我們保證可以在只使用內(nèi)通道的情況下從任意一個(gè)大廳走到另一個(gè)大廳。如果我們規(guī)定不重復(fù)走通道，則方案唯一
通過這些限制我們可以提煉出如下信息以便我們解題:
1、將所有外邊刪掉 該圖就是一棵樹 而且是平衡二叉樹
2、將外廳按順時(shí)針序(逆時(shí)針同理)排序則可行路徑上的外廳一定是遞增的
這道題目的解法有很多種 我想到的就有3種
一：樹形動(dòng)態(tài)規(guī)劃
不考慮外邊 設(shè)f[i]表示以i為根節(jié)點(diǎn)的子樹上的最小花費(fèi)
先初始化每一條外邊 在兩端點(diǎn)的最近公共祖先上記錄在最近公共祖先上
開始動(dòng)態(tài)規(guī)劃 對(duì)于每一個(gè)i枚舉記錄在它上的外邊 費(fèi)用為兩端點(diǎn)的路徑上的費(fèi)用+不在路徑上的f[u]

太晚了 其他的明天再說