还在写随机化？错完了！

· · 题解

来看看确定性做法，全对！！1

假设路径经过的 k+1 个点依次为 p_1,p_2\dots p_{k+1}，其中 p_1=p_{k+1}=1，那么没有奇环其实就是限制了 p 的奇数位和 p 的偶数位没有相同元素。

我们可以先固定奇数位的剩余 \frac{k}{2}-1 个点，对于相邻两个奇数位的点 (u,v)，找一个偶数位的点 w 使得 u\to w\to v 最短。（因为奇偶位置独立，偶数位内部是可以重复经过点的，所以每个奇数点的相邻 pair 是独立的）

每次搜完奇数位的点之后对于每个 (u,v) 枚举 w 的时间复杂度为 \mathcal O(n^{\frac{k}{2}})，过不了。考虑预处理，对于每个 (u,v)，预处理前 \frac{k}{2}+1 优的 w，搜索的时候枚举前 \frac{k}{2}+1 优解中第一个没有出现在奇数点集里的点即可。预处理复杂度 \mathcal O(n^3k)，搜索复杂度 \mathcal O(kn^{\frac{k}{2}-1})，可以通过。

反观随机化，理论上应当随机 2^k 次染色，期望复杂度 \mathcal O(2^kkn^2)，还有约 10^{-6} 的概率不能得到正确答案，错完了！！1

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=85,INF=1e15;
ll n,k,a[N][N],d[N][N][7],r[N],ans=INF,v[N];
ll calc(ll i,ll j,ll k){
    if(!k)return INF;
    return a[i][k]+a[k][j];
}
void dfs(ll x){
    if(x>k/2){
        ll res=0;
        rep(i,1,k/2-1){
            rep(p,0,5){
                if(!v[d[r[i]][r[i+1]][p]]){
                    res+=calc(r[i],r[i+1],d[r[i]][r[i+1]][p]);
                    break;
                }
            }
        }
        rep(p,0,5){
            if(!v[d[r[k/2]][r[1]][p]]){
                res+=calc(r[k/2],r[1],d[r[k/2]][r[1]][p]);
                break;
            }
        }
        ans=min(ans,res);
        return ;
    }
    rep(i,1,n){
        r[x]=i;
        v[i]++;
        dfs(x+1);
        r[x]=0;
        v[i]--;
    }
}
int main(){
    n=read(),k=read();
    rep(i,1,n){
        rep(j,1,n)a[i][j]=read();
    }
    rep(i,1,n){
        rep(j,1,n){
            rep(k,1,n){
                if(k==i||k==j)continue;
                d[i][j][6]=k;
                per(p,5,0){
                    if(calc(i,j,d[i][j][p+1])<calc(i,j,d[i][j][p]))swap(d[i][j][p+1],d[i][j][p]);
                    else break;
                }
            }
        }
    }
    r[1]=1,v[1]=1;
    dfs(2);
    write(ans);
    return 0;
}