程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ural 1143. Electric Path(凸包上最短哈密頓路徑)

ural 1143. Electric Path(凸包上最短哈密頓路徑)

編輯：C++入門知識

題意：逆時針給一個凸包的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