开场 10 分钟就有人过的 1D ,你值得拥有!

$\texttt{swap(B, D)}$ 警告。

精读题面,发现 $k \le 10$ ,考虑从这个性质中寻找解法。

$k \le 10$ 意味着最后真正对结果产生贡献的节点只会有 $10$ 个以下。

结合题面中给出的「没有奇环」条件,容易想到二分图黑白染色。

考虑对每个点随机染 黑 / 白色,再强制走两端颜色 不相同 的边。

这个过程可以用简单 dp ,$f_{i, j}$ 表示走了 $i$ 条边,当前在节点 $j$ 的最小花费,$\Theta(n^2k)$ 直接转移即可。

重复这个过程若干遍即可。

我们继续考虑为什么这个解法是大概率正确的。

考虑如果我们已经知道了最终的一条最优路径,这上面最多有 $k$ 个点。

那么这 $k$ 个点在一种染色方案中黑白相间的概率是 $\frac{1}{2^{k - 1}}$ ,在 $k = 10$ 的情况下就是 $\frac{1}{512}$。

随机 $5000$ 次的情况下,随不出正确答案的概率是 $(\frac{511}{512})^{5000} \approx 0.000056845461206$ ,非常小,可以忽略不计。

这解法就 ** 离谱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647

int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

ll f[20][100], dis[100][100];
int c[100];

int main(){
srand((unsigned)time(NULL));
int n = inp();
int k = inp();
int T = 5000;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = inp();
ll ans = 1e18;
while(T--){
for(int i = 1; i <= n; i++){
c[i] = rand() & 1;
f[0][i] = 1e18;
}
f[0][1] = 0;
for(int i = 0; i < k; i++){
for(int j = 1; j <= n; j++)
f[i + 1][j] = 1e18;
for(int j = 1; j <= n; j++)
for(int u = 1; u <= n; u++)
if(c[j] != c[u])
f[i + 1][u] = std::min(f[i + 1][u], f[i][j] + dis[j][u]);
}
ans = std::min(ans, f[k][1]);
}
printf("%lld\n", ans);
}

 评论