P1522 [USACO2.4]牛的旅行 Cow Tours

思路

• 牧区可以抽象成图上每一个点
• 牧场可以看作连通块
• 新牧场的最大直径=两点到未连通前两个牧场的最大距离（保证满足题意：一个牧场的直径就是牧场中最远的两个牧区的最短距离）+两点之间最短距离

实现

• 邻接矩阵存图
• floyed计算连通块内最短距离
• 一个数组存储点到它所在的连通块的最大距离
• 枚举任意两点，记录添加后最大距离

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>using namespace std;int n;
const int inf=0x3f3f3f3f;
const int maxn=200;
double mp[maxn][maxn];
int k=0;
int f[maxn];
double disf[maxn];
struct nodep{int x,y;
}p[maxn];
double ans;
double ll=0;
double disd(int x,int y){return sqrt((p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)*(p[x].y-p[y].y));
} 
int main(){scanf("%d",&n);memset(disf,0,sizeof(disf)); memset(mp,0,sizeof(mp));for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);char c[maxn]; for(int i=1;i<=n;++i){scanf("%s",c);int len=strlen(c);for(int j=1;j<=len;++j){if(c[j-1]=='1') mp[i][j]=disd(i,j); else if(i!=j) mp[i][j]=inf*1.0;}}//floyedfor(int kk=1;kk<=n;++kk)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)mp[i][j]=min(mp[i][j],mp[i][kk]+mp[kk][j]);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){//因为把图上的最短路已经算出，所以 每个点所能到达的最大值 即最远两个点的图上的最短距离if(mp[i][j]!=inf) disf[i]=max(disf[i],mp[i][j]);//求每个点能连通的最大距离ll=max(ll,disf[i]);//未添加路径前的最大直径 }double lll=inf;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(mp[i][j]==inf)//枚举每一种添加边的情况，取最小值 lll=min(disf[i]+disd(i,j)+disf[j],lll);//未连通的两个点添加图上的一条边最短距离+这两点分别到本图上的最短距离即为新图的直径ans=max(ll,lll);printf("%.6f",ans);return 0; 
}

此题需要理清楚概念（比较绕