题目链接

题目描述

给定一个完全图，路径带权且 $dis(i,j)$ 不一定等于 $dis(i,j)$ ​ 边数为 $k$ 不存在奇环且起点和终点都是 $1$ 的最小路径

$n \le 80$

$k \le 10$

简要做法

每个点随机染色，每次只能走两端颜色不同的边

这样的话可以 $O(k \cdot E) = O(kn^2)$ dp 出答案

对于一条最优路径，这上面最多 $k$ 个点

这条路径不合法的概率为 $1 - \frac{1}{2^{k-1}} = \frac{511}{512}$

随机 $512 \cdot 20$ 次的情况下，随不到正解的概率是 $\left(\frac{511}{512}\right)^{512 \cdot 20} \approx e^{-20} \approx 2\cdot 10^{-9}$

参考代码

#include <stdio.h>
#include <algorithm>
#include <time.h>

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

const int N = 80 + 5;
const int K = 10 + 5;
const int INF = 0x3f3f3f3f;

int n, k, ans = INF;
int col[N];
int dis[N][N], f[K][N];

int main()
{
    srand(unsigned(time(NULL)));
    n = read(), k = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = read();
    for (int T = 512 * 20; T--;)
    {
        for (int i = 1; i <= n; i++)
            col[i] = rand() & 1, f[0][i] = INF;
        f[0][1] = 0;
        for (int i = 0; i < k; i++)
        {
            for (int j = 1; j <= n; j++)
                f[i + 1][j] = INF;
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++)
                    if (col[u] ^ col[v])
                        f[i + 1][v] = std::min(f[i + 1][v], f[i][u] + dis[u][v]);
        }
        ans = std::min(ans, f[k][1]);
    }
    return printf("%d", ans), 0;
}