题解：CF1310D Tourism

· · 题解

随机化是个好东西。

看到没有奇环，可以想到二分图。
想到二分图，就可以想到染色法。

因此，u \to v 当且仅当两个点颜色不同。
但题目中一点关于颜色的信息都没有，怎么办？

还有随机化！

随机给每一个点分配颜色即可。
然后就是 dp：

dp_{i,st}=\min_{col_i \ne col_j} {dp_{j,st-1} + dist_{i,j}}

其中，dp_{i,st} 为走了 st 步后到了 i 的最大距离，col_i 表示颜色，dist_{i,j} 表示距离。

初始化：dp_{1,0}=0。
答案：dp_{1,k}。

当然随机化一次很可能出错，所以要多来几次。自测 3000 次没有问题（当然也说不准）。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=85;
int a[N][N],f[N][N]; 
int d[N];
int main(){
    srand(time(NULL));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int T=3000;
    int ans=2e9;
    while(T--){
        for(int i=1;i<=n;i++){
            d[i]=rand()%2;
        }
        memset(f,0x3f,sizeof f);
        f[1][0]=0;
        for(int k=1;k<=m;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(d[i]!=d[j]){
                        f[i][k]=min(f[i][k],f[j][k-1]+a[i][j]);
                    }
                }
            }
        }
        ans=min(ans,f[1][m]);
    }
    cout<<ans;
}