题解 CF1314D Tourism

开场 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$ ，非常小，可以忽略不计。

这解法就 ** 离谱。

#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);
}

Dilute

题解 CF1314D Tourism