1. c==0时要赋inf
2. ans取Min
3. ans初始值inf
4. ans更新时要用牧场距离
暂时这些,其他问题未找到,暂时还是过不去,先fix吧
by appIe365 @ 2023-01-03 16:55:45
@[_1118_](/user/902195) 我全改了,还是过不了样例
by Luckies @ 2023-01-03 17:02:00
```
/*
* maxi表示的应该是每个点与所在连通块的距离最远的点的最远距离
* 最终答案应该是 某两不连通的点 i 和 j 到距离各自最远的点的最远距离和 i 和 j 的距离之和,i 所在连通块最大距离,j 所在连通块的最大距离,三者取最大值。
* 您理解成了 i 所在连通块最大距离,而应该是 i 到距离自己最远的点的最远距离。
*/
```
by im0use @ 2023-01-03 19:28:37
你的代码有几处我认为的错误,比如
- 算dist用int可以会溢出
- memset(g, 0x3f, sizeof g)这个不起作用
- 对题目的理解可能有问题,ans的计算是将两个不连通的牧区连接,所以这三个值分别是
- i 自己的距离加上 j 自己的距离 加上 i 和 j 的距离 maxi[i] + maxi[j] + get_dis(i, j)
- i 所在连通块的最大距离 maxi[find(i)]
- j 所在连通块的最大距离 maxi[find(j)]
我将你的代码修改了,你原先写的我将其注释掉了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 55;
struct node
{
int x, y;
}a[N];
int n, fa[N];
double g[N][N], ans = -1e9, maxi[N];
double get_dis(int x, int y)
{
double dx = 1ll * (abs(a[x].x - a[y].x)) * (abs(a[x].x - a[y].x));//这里有改动,int可能会溢出
double dy = 1ll * (abs(a[x].y - a[y].y)) * (abs(a[x].y - a[y].y));
return sqrt(dx + dy);
}
int find(int x)
{
if (fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx == fy)
return;
if (maxi[fy] < maxi[fx]) fa[fy] = fx;//这里有改动,按值merge
else fa[fx] = fy;
return;
}
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
return;
}
int main()
{
cin >> n;
// memset(g, 0x3f, sizeof(g));注意对浮点数这样做,是将每个数变成0.几,所以这样赋值是错误的。
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = 0x3f3f3f3f;//手动赋初值
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
for (int i = 1; i <= n; i++)
g[i][i] = 0;
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
char c;
cin >> c;
if (c == '1')
{
double w = get_dis(i, j);
g[i][j] = w;
//merge(i, j); 我的想法是按大小merge,就是最终连通块中点都merge到最大距离的点上面,所以不在开始的时候merge
}
}
floyd();
/*
* maxi表示的应该是每个点与所在连通块的距离最远的点的最远距离
* 最终答案应该是 某两不连通的点 i 和 j 到距离各自最远的点的最远距离和 i 和 j 的距离之和,i 所在连通块最大距离,j 所在连通块的最大距离,三者取最大值。
* 您理解成了 i 所在连通块最大距离,而应该是 i 到距离自己最远的点的最远距离。
* 所以求 maxi 的时候先不要用dsu
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
int fx = find(i), fy = find(j);
if (fx == fy)
maxi[fx] = max(maxi[fx], g[i][j]);
}
*/
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] < 0x3f3f3f3f)
maxi[i] = max(maxi[i], g[i][j]);//这里有新增,先求出maxi,然后按照maxi的值进行merge
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (g[i][j] < 0x3f3f3f3f)
merge(i, j);//这里有新增,按值进行merge
ans = 0x3f3f3f3f;//这里有改动,求最小值先赋最大
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
/*
* 1. 应该是 i 自己的距离加上 j 自己的距离 加上 i 和 j 的距离 maxi[i] + maxi[j] + get_dis(i, j)
* 2. i 所在连通块的最大距离 maxi[find(i)]
* 3. j 所在连通块的最大距离 maxi[find(j)]
* 三者取最大值
* 然后再与ans取最小值
int fx = find(i), fy = find(j);
if (fx != fy)
{
double dis = get_dis(i, j);
double mx = maxi[fx], my = maxi[fy];
ans = max(ans, max(mx + my + dis, max(mx, my)));
}
*/
if (g[i][j] >= 0x3f3f3f3f)//这里有改动,保证两点不能连通
ans = min(ans, max(maxi[i] + maxi[j] + get_dis(i, j), max(maxi[find(i)], maxi[find(j)])));
}
cout << fixed << setprecision(6) << ans;
return 0;
}
```
by im0use @ 2023-01-03 20:01:42