题解：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

次没有问题（当然也说不准）。

代码

CPP

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

题解：CF1310D Tourism

文章操作

代码

相关推荐

评论

题解：CF1310D Tourism