首页 > 代码库 > 洛谷OJ 1433 吃奶酪 暴力dfs(最优性cut)
洛谷OJ 1433 吃奶酪 暴力dfs(最优性cut)
https://www.luogu.org/problem/show?pid=1433
题意:起点为(0,0) 有n个点 求出起点出发经过n个点的最小距离
//15个点 暴力 + 最优性cut(sum+还剩的点*最小距离>=ans 则stop) 水过...
#include <bits/stdc++.h> using namespace std; typedef pair<int,double> pii; const int N=2e3+20; const double inf=1e7; struct node{ double x,y; }a[N]; int n; double d(int i,int j) { double dx=a[i].x-a[j].x; double dy=a[i].y-a[j].y; return sqrt(dx*dx+dy*dy); } double ans,mn; double dist[N][N]; int vis[N]; void dfs(int cur,double sum,int cnt) { if(sum+(n-cnt)*mn>=ans)//最优性cut return; if(cnt==n) { ans=min(ans,sum); return; } for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i]=1; dfs(i,sum+dist[i][cur],cnt+1); vis[i]=0; } } } int main() { while(cin>>n) { memset(vis,0,sizeof(vis)); mn=ans=1e7; for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y; a[0].x=a[0].y=0; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(i==j) continue; dist[i][j]=d(i,j); mn=min(mn,dist[i][j]); } } dfs(0,0,0); printf("%.2lf\n",ans); } return 0; }
洛谷OJ 1433 吃奶酪 暴力dfs(最优性cut)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。