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

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

沒有兩條通道相交。

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

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

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

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

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

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

太晚了 其他的明天再說