题解 CF1310D 【Tourism】
Dilute
·
·
题解
\color{darkblue}\Huge\texttt{My blog}
开场 10 分钟就有人过的 1D ，你值得拥有！
精读题面，发现 k \le 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$ ，非常小，可以忽略不计。
这解法就 ** 离谱。
```cpp
#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);
}
```