首页 > 代码库 > CodeVS 1344 线型网络

CodeVS 1344 线型网络

2024-08-13 00:31:06   210人阅读

Sol

随机化算法+哈密顿路径.

好厉害的题...首先都会想到状压DP对吧,复杂度 \(O(n^2 2^n)\) .

\(n=20\) 技术分享 exm?? \(10^8\)

有一种算法就是随机化算法 再调整.

通过随机化算法,再 \(O(n^2)\) 来调整.

调整方式如下:

如果有 \(dis(i-1,i)+dis(j,j+1)>dis(i-1,j)+dis(i,j+1)\) 

那么就将区间 \([i,j]\) 翻转...

非常神奇吧 关于证明原文中并没有,总之这样会导致很多不同的方案收束到同一方案,造成方案数的减少,来以随机概率获得正确结果.

PS:简直就是骗分神奇的方法...

原文链接:http://www.doc88.com/p-772451936672.html

Code

#include<cstdio>#include<cmath>#include<ctime>#include<utility>#include<cstdlib>#include<algorithm>#include<iostream>using namespace std;const int N = 25;#define mpr(a,b) make_pair(a,b)#define sqr(x) ((x)*(x))int n,T;pair<int,int> p[N];int a[N];double d[N][N];double ans=9999999999.0;inline int in(int x=0,char ch=getchar(),int v=1){	while(ch!=‘-‘&&(ch>‘9‘||ch<‘0‘)) ch=getchar();if(ch==‘-‘) v=-1,ch=getchar();	while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x*v; }double dis(int u,int v){ return sqrt((double)sqr(p[u].first-p[v].first)+sqr(p[u].second-p[v].second)); }int main(){	srand(time(0));	n=in();	for(int i=1;i<=n;i++) p[i]=mpr(in(),in()),a[i]=i;	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=dis(i,j);	//	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%.2lf%c",d[i][j]," \n"[j==n]);//	for(int i=1;i<=n;i++) cout<<p[i].first<<" "<<p[i].second<<endl;		for(T=2000;T--;){		random_shuffle(a+1,a+n+1);		double tmp=0;		//		cout<<"***********"<<endl;//		for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;				for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++)			if(d[a[i-1]][a[i]]+d[a[j]][a[j+1]]>d[a[i-1]][a[j]]+d[a[i]][a[j+1]]) reverse(a+i,a+j+1);		for(int i=1;i<n;i++) tmp+=d[a[i]][a[i+1]];		//		cout<<"***********"<<endl;//		for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;//		cout<<"tmp="<<tmp<<endl;				ans=min(ans,tmp);	}printf("%.2lf\n",ans);	return 0;}

　　

CodeVS 1344 线型网络


联系
我们