首页 > 代码库 > 【USACO 2.4】Cow Tours （最短路）
【USACO 2.4】Cow Tours （最短路）
题意：给你n（最多150）个点的坐标，给出邻接矩阵，并且整个图至少两个联通块，现在让你连接一条边，使得所有可联通的两点的最短距离的最大值最小。
题解：先dfs染色，再用floyd跑出原图的直径O($n^3$)，然后枚举新增的边的端点O($n^2$)，再分别找出到边端点距离最远的点($n$)，那么添加这条边后新图的直径要么是原图直径要么就是两个端点到各自最远点的距离之和加上边的长度。每次维护最小的直径。这样总的是O($n^3$)。
代码：
/*TASK:cowtourLANG:C++*/#include<cstdio>#include<algorithm>#include<cmath>const double INF=0x3f3f3f3f;using namespace std;#define N 155int n,x[N],y[N],b[N];int color;double ans;double d[N][N];double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}void dfs(int x){ b[x]=color; for(int i=1;i<=n;i++) if(d[x][i]!=INF&&!b[i]) dfs(i);}int main(){ freopen("cowtour.in","r",stdin); freopen("cowtour.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d %d ",&x[i],&y[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)d[i][j]=INF; for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++){ char c=getchar(); if(c==‘1‘) d[i][j]=dis(i,j); } for(int i=1;i<=n;i++) if(!b[i]){ color++; dfs(i); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)if(i!=j) if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)if(d[i][j]!=INF) ans=max(ans,d[i][j]); double m=INF; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)if(b[i]!=b[j]){ double d1=0,d2=0; for(int k=1;k<=n;k++){ if(d[i][k]!=INF) d1=max(d1,d[i][k]); if(d[k][j]!=INF) d2=max(d2,d[k][j]); } m=min(m,d1+d2+dis(i,j)); } printf("%f\n",max(m,ans)); return 0;}
【USACO 2.4】Cow Tours （最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。