codevs1344线型网络

关键词：

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]," 
"[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
",ans);
	return 0;
}

cogs6.线型网络

6.线型网络★★☆  输入文件：linec.in  输出文件：linec.out   简单对比时间限制：1s  内存限制：256MB【问题描述】有 N(N<=20)台PC放在机房内，现在要求由你选定一台PC，用共N−1条网线从这... 查看详情

身份证识别基于matlabbp神经网络身份证号码识别含matlab源码1344期

一、身份证号码识别简介（附课题作业报告）1引言当今是一个信息高度发达的时代，对于每个公民而言身份证那一连串的数字体现了个人信息的唯一性，出于保障公民合法权益和社会治安的考虑，越来越多的行业都开始建立自... 查看详情

codevs1034家园——网络流

由数据范围看是可以用网络流的。。。其实还是接近于很裸的网络流，不过是变成了动态建边，图会很大，不过题目数据范围小啊。。。枚举时间，自己想一个上界，cyc大佬说是100，那就100吧，到达上界前找到就输出当前时间并... 查看详情

codevs1243网络提速

1243网络提速时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题目描述 Description某学校的校园网由n(1<=n<=50)台计算机组成，计算机之间由网线相连，如图5。其中顶点代表计算机，边代表网线。正如你所见，不同网线... 查看详情

codevs1088神经网络

/*这题目简直没谁了我只想说codevs上传题目的专业素养在哪里最起码别有错别字啊0.0咳咳说正事应该是考察拓扑排序的统计出入度然后依次处理每个入度为0的点当然ci为0的可以不必要统计了因为他不传递刺激好好理解一下给出的... 查看详情

洛谷p1038神经网络==codevs1088神经网络

P1038神经网络题目背景人工神经网络（ArtificialNeuralNetwork）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自... 查看详情

codevs1490[ctsc2008]网络管理

...部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部... 查看详情

codevs1243网络提速

题目描述 Description某学校的校园网由n(1<=n<=50)台计算机组成，计算机之间由网线相连，如图5。其中顶点代表计算机，边代表网线。正如你所见，不同网线的传输能力不尽相同，例如计算机1与计算机2之间传输信息需要34秒... 查看详情

[codevs1243]网络提速

题目大意：有n台电脑，m个加速器，每台电脑之间传输文件有一个时间，每个加速器可以使传输时间减半（两台电脑之间可以有多个加速器），求电脑1传输文件到电脑n的最短时间。解题思路：有些人先求出最短路径，再每次找... 查看详情

洛谷p1262间谍网络==codevs4093ez的间谍网络

4093EZ的间谍网络时间限制:10s　　　　空间限制:128000KB　　　　题目等级:黄金Gold题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受... 查看详情

codevs3730无线网络发射选址

题目描述 Description随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平... 查看详情

codevs1922骑士共存问题——网络流

给棋盘黑白染色，源点向不为障碍的奇点连一条权值为1的边，向可以攻击到的偶点连一条边，权值为inf；偶点向汇点（t=n*n+1）连一条权值为1的边。跑最小割，最小割的意义就是看至少要放弃几个点（即这里不放骑士）才能使他... 查看详情

1344.anglebetweenhandsofaclock(m)(代码片段)

AngleBetweenHandsofaClock(M)题目Giventwonumbers,hourandminutes.Returnthesmallerangle(indegrees)formedbetweenthehourandtheminutehand.Example1:Input:hour=12,minutes=30Output:165Example2:Input:hour=3,minut 查看详情

1344走格子

1344走格子基准时间限制：1秒空间限制：131072KB分值:5 难度：1级算法题有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A[i]，表示... 查看详情

51nod1344

纪念第10题1级算法题直接贴代码了#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;scanf("%d",&n);longlongans=0,sum=0,x;for(inti=1;i<=n;i++){scanf("%lld",&x);sum-=x;ans=max(ans,sum);}printf("%l 查看详情

codevs1062路由选择

...目等级:钻石Diamond题目描述 Description   在网络通信中，经常需要求最短路径。但完全用最短路径传输有这样一个问题：如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出... 查看详情

codevs1993草地排水

【算法】网络流-最大流(dinic)【题解】网络流：http://m.blog.csdn.net/article/details?id=9401909当前弧优化是因为DFS过程中访问x点时一旦流入量=流出量就退出，所以可以记录下此时正在考虑的弧，下次从此处继续考虑即可。当前弧之前的... 查看详情

51nod1344走格子（贪心

1344 走格子 有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A[i]，表示这个格子的能量值。如果A[i]>0，机器人走到这个格子... 查看详情