ural 1143. Electric Path(凸包上最短哈密顿路径) - c++编程基础

TOP

ural 1143. Electric Path(凸包上最短哈密顿路径)

2015-07-24 05:49:52 来源: 作者: 【大中小】浏览:4次

题意：逆时针给一个凸包的n(n<=200)个顶点坐标，求一个最短哈密顿路径的长度。

解法：求最短哈密顿本身是一个NP问题，但是因为是凸包上，可以利用这个做；有一个性质：凸包上的最短哈密顿路径不会出现交叉。所以可以看出来从一点出发，他要么和顺时针相邻点连接，要么和逆时针相邻点相连接；通过这个性质可以通过dp做：

ans[i][j][0]表示i开始，往后j的点最短路径长度，ans[i][j][0]表示i开始，往前j的点最短路径长度；

转移方程见代码：有了转移方程枚举第一个起始位置就行，复杂度n^3.

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               //freopen (in.txt , r , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=210; const int INF=1e9+7; struct point { double x,y; void read() { scanf(%lf%lf,&x,&y); } } points[Max]; double dist[Max][Max]; int t=0; int n; double getdis(int i,int j) { return dist[(i+t)%n][(j+t)%n]; } double getdist(int i,int j) { i=(i+n)%n; j=(j+n)%n; return sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x)+ (points[i].y-points[j].y)*(points[i].y-points[j].y)); } double ans[Max][Max][2]; double dfs(int i,int j,int st) { i=(i+n)%n; if(!zero(ans[i][j][st])) return ans[i][j][st]; if(j==1) return ans[i][j][st]=getdis(i,i+(st?-1:1)); if(!st) return ans[i][j][st]=min(dfs(i+1,j-1,0)+getdis(i,i+1),dfs(i+j,j-1,1)+getdis(i,i+j)); else return ans[i][j][st]=min(dfs(i-1,j-1,1)+getdis(i,i-1),dfs(i-j,j-1,0)+getdis(i,i-j)); } double solve() { memset(ans,0,sizeof ans); return min(dfs(1,n-2,0)+getdis(0,1),dfs(n-1,n-2,1)+getdis(0,n-1)); } int main() { scanf(%d,&n); for(int i=0; i
              
               ?
               ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++ mem_fun 和 mem_fun_ref 的用..	下一篇：C++语言笔记系列之十一――友元函..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: