题解 CF1314D Tourism

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

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

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

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

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

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

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

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

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

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

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

随机 50005000 次的情况下,随不出正确答案的概率是 (511512)50000.000056845461206(\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);
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。