[CF1310D] Tourism

题目链接

Solution

给定一个带权完全图，求从 $1$ 出发走 $k$ 条边回到 $1$ 且路径中没有奇圈的最小距离。

如果忽略“没有奇圈”这个条件，就是一个简单的 dp：设 $dp[i][j]$ 表示用 $j$ 步走到 $i$ 的最小距离，则：$dp[i][j]=\min\limits_{1\leq r\leq n \wedge r\neq i}dp[r][j-1]+w_{r,i}$. 复杂度为 $O(n^2k)$.

回忆奇圈的充要条件：一个图是二分图当且仅当该图不含奇圈。所以我们把原图二染色，即相当于删掉一些边使之成为二分图，然后再 dp。

然而暴力 $O(2^n)$ 二染色不可取，于是我们就……随机化！算一算正确概率：答案路径长为 $k$，只要它被染成“黑-白-……”或“白-黑-……”就得到了正确答案，所以正确概率是 $\frac{2}{2^k}=2^{1-k}\geq\frac{1}{512}$. 只要我们做 $5000$ 次，错误概率就是 $\left(\frac{511}{512}\right)^{5000}=5\cdot10^{-5}$.

复杂度 $O(5000\cdot n^2k)$，极限数据 $3e8$，然后就看评测机给不给力了（CF 的评测机无压力）

Code

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<ctime>

using namespace std;

typedef long long LL;

const int N = 85;

int n, k, col[N];
LL g[N][N], dp[N][15], ans = 1e16;

inline void solve(){
    memset(dp, 0x7f, sizeof dp);
    dp[1][0] = 0;
    for(int j = 1; j <= k; j++){
        for(int i = 1; i <= n; i++){
            for(int r = 1; r <= n; r++){
                if(col[r] == col[i])    continue;
                dp[i][j] = min(dp[i][j], dp[r][j-1] + g[r][i]);
            }
        }
    }
    ans = min(ans, dp[1][k]);
}

int main(){
    srand(time(NULL));
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%lld", &g[i][j]);
    for(int _ = 1; _ <= 5000; _++){
        for(int i = 1; i <= n; i++)
            col[i] = rand() % 2;
        solve();
    }
    printf("%lld\n", ans);
    return 0;
}