对于这道题,经过分析,我们发现:
对于每一个点,一定会有一个点与他联通且与他的距离最远.
再看一眼n的范围,果断使用Floyd算法.
先求出每一个点到其他点的距离,找出用Maxstep[i]代表与点i相距最远的点距离点i的距离.
先记录一下最大的Maxstep[i],记为ans1.
再考虑加边(注意加边必须加在不连通的两个点之间):
我们枚举每一对不连通的点对,考虑在这两个点加边.
加完边后,我们注意到此时的直径应该是Maxstep[i]+dis(i,j)+Maxstep[j].
我们再找出此时最短的一条Maxstep[i]+dis(i,j)+Maxstep[j],记为ans2.
最终答案记为max(ans1,ans2).
Floyd算法标准时间复杂度 $O(n^3)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 99999999
struct city{
int x,y;
}p[200];
double step[200][200],Maxstep[200],ans1,ans2=MAXN;
int n,m,Maps[200][200];
char Map;
void F()
{
for(int k=1;k<=n;k++)//Floyd算法标准三重循环
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(step[i][j]>step[i][k]+step[k][j])
step[i][j]=step[i][k]+step[k][j];
}
double len(int x1,int y1,int x2,int y2)
{
return sqrt(pow((x1-x2),2)+pow((y1-y2),2));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&p[i].x,&p[i].y);//记录坐标
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>Map;
Maps[i][j]=Map-'0';//获取基本信息
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(Maps[i][j])
step[i][j]=len(p[i].x,p[i].y,p[j].x,p[j].y);//记录信息
else if(i!=j)
step[i][j]=MAXN;//不连通记录为正无穷
}
F();//Floyd算法
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(step[i][j]!=MAXN)
Maxstep[i]=max(step[i][j],Maxstep[i]);
ans1=max(ans1,Maxstep[i]);//先求ans1
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(step[i][j]==MAXN)
ans2=min(Maxstep[i]+len(p[i].x,p[i].y,p[j].x,p[j].y)+Maxstep[j],ans2);//再求ans2
double ans=max(ans1,ans2);//最终答案取max
printf("%.6lf",ans);
return 0;
}
纪录没好生活
纪录没好生活
ans2不是路径的最大值吗,不是题目求的直径的最大值呀
原来的两个连通块是不连接的,也就是互连的(i,j)原来之间是没有边的。现在把i,j连上了,有了边,此边一定是两家人互相走亲戚的必经之路。也就是说,如果直径存在于两个连通块之间,那么必定经过i,j,即maxd(i)+maxd(j)+get(i,j)。当然,也可能直径不过i,j,因为你连的这条边,最终形成的连通图,直径并不是在新边上,而是原来的老直径真牛X,原来的老直径不是一个一个连通块单独计算的,而是用了一个比较巧妙的方法:获取了整体上所有连通块的最长老直径!有点像DP的按类聚合噢,不是一个一算,而是整体算,这个想法选牛B的。
为什么还要取max呢,最终答案记为max(ans1,ans2).
题目中直径指的是牧场中最远的两个牧区的距离,所以最后要取大值
要考虑到牧场中最远的两个牧区初始在同一个牧场中的情况
这样的话牧场应该只有一个才对,否则连接端点和另一个牧场任一点就可以了
为什么呢?
理论上来讲这种说法是部分正确的。
因为我们指的是最优连接。所以非最优连接是有可能产生比这还要大的直径的。
不过可能会存在多种连接方式可以产生此直径。
这道题只求了最小直径是多少,所以到底采用那种连接并不需要在考虑范围内。
所以是可以有多个牧场滴~
感谢回复,我的想法是对“初始最远的两点在同一牧场”的反例,采用了反证法:
假设牧场中最远的两个牧区在同一个牧场,那么连接其中的一点和另一牧场,得到的边一定>ans1的答案,也就是说连接后的所有可能答案,已经大于ans1,不需要再取max。
回复最优连接:枚举的过程是所有可能的连接边(即所有不在同一牧场的边),如果这一次枚举的并不是最优连接也没有关系,因为下一次下下次,总会枚举到最优边。枚举到最优边的那一次是不会被遗漏的,也是包含ans1的。
可能产生的误会:连接后牧场的合成牧场的直径最大值可能不变。
任意牧场不论直径为多少,两牧区的距离不可能为0。只要连接那个最长直径的端点,除非:
1.连接的两牧区是在同一坐标 2.另一牧区到最远点距离为0 3.只有一个牧场,不存在另一个牧场
否则只要连接,直径就会变大。
所以如果存在答案,答案必然不是同一牧场的两个点,因为不论怎样连接那两个点,都会产生更大的直径。
那不一定。它求的是“最小直径”。
那么我们来分两种情况:
1.如你所说,只要连接,直径就会变大
确实答案存在于不同牧场的两个点。
2.其实连接后直径不一定变大。比如其中一个牧场的直径真的长得离谱。
这时其实真的有可能在同一牧场中。
比如这组数据:
4
0 0
1000 0
500 1
500 0
0101
1001
0000
1100
如果输出中间结果,就会得到:
ans1=1000,ans2=501
意思是这是直角坐标系,距离不是由边确定的,是由坐标确定的吗?所以联通不一定变大
这道题的意思是若干个点之间有连接。
有连接的两个点之间的距离就是平面直角坐标系中那两个点的距离。
因为直径指的是“离得最远的两个点之间的距离”。
所以如果两个牧场的直径差实在太大,就有可能出现连接后直径在原先的其中一个牧场的情况。
明白了,感谢!
原来是还有更优情况啊!感谢回复!感谢你构造的数据!
如果题目要求的是联通后的牧场直径尽可能大,那么你的思路就是正确的。题目要求的是尽可能小,所以第一种情况就不能被忽略
刚看不理解,画了图就理解了哈哈哈
大佬您好!在样例中,为何不能直接连接AF?
?哪来的AF?
是题意理解错了吗?题目意思是图一和图二是两种不同情况的样例
%%%
tql
为什么maxstep[i]就是所在连通块的距离最大值讷
maxstep[i]是i所在连通块距离i的所有点中与i距离的最大值