当然本题也可以通过状态压缩 DP 做到 $\mathcal O(2^n n^2)$ 的复杂度。
开 $n=8$ 是因为放在这个位置被钦定使用枚举全排列通过，作者写了一份 Python 代码发现 $n=9$ 就跑的很慢了。
另外 C++ 注意要开 `long long`，其他语言同理。
---
第一档部分分每次选度数最小的出来做。第二档其实也是，但是因为树的特殊性质边权之和就是答案。
刻意卡了一下每次选度数最小或者是代价最小的拉出来跑贪心或者凭这个性质做搜索的剪枝。分别被卡到了 $70$ 分和 $60$ 分。
---
关于题目名称，和本场比赛彩蛋有关。
---
这是我写的 std。
```cpp
// std
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
typedef long long ll;
int n, m;
vector<array<int, 2>> a[30];
bool vis[30];
bool del[30];
int v[30];
ll ans = 1e18;
void dfs(int dep)
{
if (dep == n + 1)
{
memset(del, 0, sizeof(del));
ll tmp = 0;
for (int i = 1; i <= n; i++)
{
int u = v[i];
int tot = 0;
ll sum = 0;
for (auto [v, w] : a[u])
{
if (del[v])
continue;
tot++;
sum += w;
}
del[u] = 1;
tmp += sum * tot;
}
chkmn(ans, tmp);
return;
}
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
v[dep] = i;
vis[i] = 1;
dfs(dep + 1);
vis[i] = 0;
v[dep] = 0;
}
}
int main()
{
cin >> n >> m;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
a[u].push_back({v, w});
a[v].push_back({u, w});
}
dfs(1);
cout << ans << '\n';
return 0;
}
```
用 GPT 4o 写了个代码结果常数太大过不去，比我写的这份慢了十倍。
```python
# Python std
n, m = map(int, input().split())
e = [[]]
for i in range(n + 1):
t = []
for j in range(n + 1):
t.append(-1)
e.append(t)
for i in range(m):
u, v, w = map(int, input().split())
e[u][v] = e[v][u] = w
vis = [0] * (n + 1)
vv = [-1] * (n + 1)
ans = 10**18
def dfs(dep):
global ans
if dep == n + 1:
dele = [0] * (n + 1)
tmp = 0
for i in range(1, n + 1):
u = vv[i]
tot = 0
sum = 0
for v in range(1, n + 1):
if e[u][v] == -1:
continue
if dele[v]:
continue
tot += 1
sum += e[u][v]
dele[u] = 1
tmp += sum * tot
ans = min(ans, tmp)
return
for u in range(1, n + 1):
if vis[u]:
continue
vis[u] = 1
vv[dep] = u
dfs(dep + 1)
vis[u] = 0
vv[dep] = -1
dfs(1)
print(ans)
```
这份是 GPT 4o 写的 Java 代码。
```java
// GPT 4o Java
import java.util.*;
public class Main {
static int n, m;
static List<int[]>[] graph;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
graph = new ArrayList[n + 1];
for (int i = 1; i <= n; ++i) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; ++i) {
int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
graph[u].add(new int[]{v, w});
graph[v].add(new int[]{u, w});
}
int[] order = new int[n];
for (int i = 0; i < n; ++i) order[i] = i + 1;
long ans = Long.MAX_VALUE;
do {
// 深复制图结构
List<int[]>[] g = new ArrayList[n + 1];
for (int i = 1; i <= n; ++i) {
g[i] = new ArrayList<>();
for (int[] edge : graph[i]) {
g[i].add(new int[]{edge[0], edge[1]});
}
}
boolean[] deleted = new boolean[n + 1];
long cost = 0;
for (int idx = 0; idx < n; ++idx) {
int u = order[idx];
int deg = 0;
long sum = 0;
for (int[] edge : g[u]) {
int v = edge[0], w = edge[1];
if (!deleted[v]) {
deg++;
sum += w;
}
}
cost += (long) deg * sum;
deleted[u] = true;
for (int[] edge : g[u]) {
int v = edge[0];
g[v].removeIf(e -> e[0] == u);
}
g[u].clear();
}
ans = Math.min(ans, cost);
} while (nextPermutation(order));
System.out.println(ans);
}
// Java 没有内建的 next_permutation，需要手写
static boolean nextPermutation(int[] arr) {
int i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
int j = arr.length - 1;
while (arr[j] <= arr[i]) j--;
swap(arr, i, j);
reverse(arr, i + 1, arr.length - 1);
return true;
}
static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
static void reverse(int[] arr, int l, int r) {
while (l < r) swap(arr, l++, r--);
}
}
```