题目大意：给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个权值，请你选择一个根节点并求出一棵生成树，规定树上每条边的代价为根节点到这条边所经过的点的数量乘以这条边的权值，问所有边的代价之和最少是多少？$1 \leq n \leq 12, 0 \leq m \leq 1000$
$70pts$
由于 $n \leq 8$，因此可以 $O(n!)$ 搜索每个点是第几个被开拓的，那么第 $i$ 个点只能由前 $i-1$ 个点转移过来，可以直接从前 $i-1$ 个点中选择一个路径最短的转移，总复杂度 $O(n! \times n^2)$。
需要注意的一点是，$m$ 可以等于 $0$，这时候应该输出 $0$ 而不是 $\inf$，以后做题一定要注意看数据范围的边界。
$100pts$
$random\text{_}shuffle$
首先，一次 $random\text{_}shuffle$ 的时间复杂度是 $O(n)$ 的。
“生日悖论，指如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%，对于60或者更多的人，这种概率要大于99%。”
我们将其转换为一般式：有 $n$ 个不同的属性，随机抽取 $m$ 个元素，至少存在两个元素属性相同的概率为
我们发现 $n=12$ 的全排列有 $479001600$ 种，用上式算出当随机 $100000$ 次时，出现两个相同排列的概率已经达到 $99.997073766496996\%$。
因此可以 $T$ 次 $random\text{_}shuffle$，然后按照 $70pts$ 的做法来做，其中 $T=\dfrac{2 \times 10^7}{n^2}$。
#include <cstdio>
#include <algorithm>
#include <ctime>
const int maxn = 2e7, inf = 0x3f3f3f3f;
int a[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int dis[15][15], ans = inf;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int min(int x, int y) {
return x < y ? x : y;
}
int main() {
srand(time(0));
int n = read(), m = read(), T = maxn / n / n;
for (int i = 1; i <= m; ++i) {
int u = read(), v = read(), w = read();
if (!dis[u][v] || dis[u][v] > w) dis[u][v] = dis[v][u] = w;
}
while (T--) {
std::random_shuffle(a + 1, a + n + 1);
int res = 0, dep[15] = {}, flag = 1;
for (int i = 2; i <= n; ++i) {
int cost = inf, pre = 0;
for (int j = 1; j <= i - 1; ++j)
if (dis[a[i]][a[j]] && (dep[a[j]] - dep[a[1]] + 1) * dis[a[i]][a[j]] < cost)
cost = (dep[a[j]] - dep[a[1]] + 1) * dis[a[i]][a[j]], pre = a[j];
if (pre == 0) {
flag = 0; break;
} else {
res += cost;
dep[a[i]] = dep[pre] + 1;
}
}
if (flag) ans = min(ans, res);
}
printf("%d\n", ans);
return 0;
}
时间复杂度 $O(\dfrac{n^2T}{2})$