主題
題目連結：
題目大意：
輸入第一列給定一正整數，代表接下來有幾筆測試資料。每筆測試資料佔一列，每列給定兩正整數 n 、 c （ 2 ≦ n ≦ 20 ， 1 ≦ c ≦ 100 ），代表有一集合 S 包含了所有可能的 n 位元的二進位制數字。
而一數字可「變換」為另一數字，若且唯若兩數的二進位表示法之中只有一個位數相異。而一次變換的成本為 c 。
而現定義變換串列 T(S) ： s1 ↔ s2 ↔ …… ↔ sk ↔ s1 ，其中 si 屬於 S 集合中的元素、「↔」代表一次合法的變換。且 T(S) 滿足：所有可能的「變換」都出現在串列至少一次。
並定義 cost(T(S)) 為所有可能的變換串列 T(S) 中，變換總成本之最小值。求 cost(T(S)) 為何？
範例輸入：
2
3 1
2 1
範例輸出：
16
4
解題思維：
首先，我們將每個二進位的變換關係畫成一個圖。例如 n ＝ 3 時，該圖為
代表 000 可變換為 001 （反之亦然）、001 可變換為 011 ……其他同理。
我們可以看出 T(S) 就是在這張圖上所走的路徑。因此，要求 cost(T(S)) 就表示我們需要一個經過所有邊（代表 T(S) 包含了所有「變換」）且最後要回到起點的路徑。
經過觀察可以看到，這個問題是一筆畫問題（見維基）的變形，因為我們需要經過所有邊。但是因為本題圖的特性，因此有可能無法一筆畫走完。所以我們需要允許某幾條邊可以走第二次，此等價於新增一條一模一樣的邊在原本的邊的「旁邊」。
如 n ＝ 3 的圖，我們允許（新增）000 ↔ 001 、010 ↔ 011、100 ↔ 101、110 ↔ 111 這四條邊。即可使整張圖用一筆畫走完，此時歐拉路徑（即一筆畫走的路徑）上經過了 16 條邊。因此 cost(T(S)) 為 16 × c 。
而如果 n ＝ 2 ，圖如下
而此圖本身就可被一筆畫畫完，因此 cost(T(S)) ＝ 4 × c 。
接著討論一般情形：
如果 n 為偶數，且每個數字有 n 個合法的變換（因為一次變動一位元）。因此畫出來的圖上的 n 個點（代表 S 內的 2 ^ n 個數字）每個都是連著偶數的邊。因此一定可以一筆畫畫完，所以cost(T(S)) 為（ 2 ^ n × n ÷ 2 ）× c 。（因為圖的邊數有 2 ^ n × n ÷ 2 條）
如果 n 為奇數，因為每個點連到奇數個邊，因此一定無法用一筆畫畫完。此時則需要像 n ＝ 3 那般允許（新增）其中的一些邊，使得每個點都連著偶數的邊。此時，我們會新增 2 ^ n ÷ 2 條邊（有 2 ^ n 個點，會多出其值一半數量的邊）。所以 cost(T(S)) ＝（ 2 ^ n × n ÷ 2 ＋ 2 ^ n ÷ 2 ） × c ＝ 2 ^ ( n － 1 ) × ( n ＋ 1 ) × c 。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
