超时的暴搜
这道题一看也是很清楚了，求一个连通部分的直径，那就肯定是 floyd 算法。根据给的邻接矩阵，可以算出图上的路径。
后来才看懂这个题目给的可能是好几个连通的子集组成的，而我要在任意两个连通域里面加任意一条边。所以我又做了一下 dfs，对各个区域染色。这样，任取 i 和 j，判断他俩不是一个连通集里的，就加一条边做 floyd。
我试了一下，floyd 这样直接算不连通的图好像是没有问题的，算出来各自内部的最短路径，不同连通域的就还是 +Inf。
其中还遇到了一些不熟悉的东西：
- double 类型的最大值，在 float.h 中有常量 DBL_MAX；
- 对于输入，这次给的是一串 1 和 0，我没有用 int，而是读成 %c ，再处理成 bool；
- sqrt 在 math.h 里；
- 输出 double 要用 %lf，前面同样可以 .6 限制小数位数。
尽管代码看起来不丑，可是到 Test 5 就超时了。
/*
ID:
LANG: C++
TASK: cowtour
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cfloat>
#include <cstring>
const int maxN = 150;
int N;
bool adj[maxN][maxN]; //邻接矩阵
double graph[maxN][maxN]; //图中距离
double dist[maxN][maxN]; //当前最短路径
int loc[maxN][2]; //坐标
int color[maxN]; //分出不同的连通域
double diameter(int x, int y, double d){
//在图中新增一条边
memcpy(dist, graph, sizeof(graph));
dist[x][y] = d;
dist[y][x] = d;
//floyd算法
for(int k = 0; k < N; k ++){
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
//找diameter
double dia = 0;
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(dist[i][j] > dia) dia = dist[i][j];
}
}
return dia;
}
void dfs(int idx, int clr){
if(color[idx]) return;
color[idx] = clr;
for(int i = 0; i < N; i ++){
if(adj[idx][i]) dfs(i, clr);
}
}
int main(){
FILE *fin = fopen("cowtour.in", "r");
FILE *fout = fopen("cowtour.out", "w");
//输入
fscanf(fin, "%d", &N);
for(int i = 0; i < N; i ++){
fscanf(fin, "%d %d\n", &(loc[i][0]), &(loc[i][1]));
}
char temp;
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
fscanf(fin, "%c", &temp);
adj[i][j] = temp - 48;
}
fscanf(fin, "%c", &temp);
}
//确定连通域
int clr = 1;
for(int i = 0; i < N; i ++){
if(!color[i]) dfs(i, clr ++);
}
//建立图
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(adj[i][j]){
graph[i][j] = sqrt(pow((loc[i][0] - loc[j][0]), 2) + pow((loc[i][1] - loc[j][1]), 2)); //勾股
}else{
graph[i][j] = DBL_MAX;
}
}
graph[i][i] = 0;
}
//不同连通域两个点连起来，再算图的直径
double minDia = DBL_MAX, dia;
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(color[j] == color [i] || adj[i][j]) continue;
dia = diameter(i, j, sqrt(pow((loc[i][0] - loc[j][0]), 2) + pow((loc[i][1] - loc[j][1]), 2)));
if(dia < minDia) minDia = dia;
}
}
fprintf(fout, "%.6lf\n", minDia);
return 0;
}
改思路
这个思路是我在吃完吉祥馄饨回来的路上想到的，后来看 nocow 上大家好像都是这么做的。
首先我在想，添加一条边，究竟造成了什么影响？能不能不去暴力重新算呢。这个新的连通域的直径，可能是：
- 含有这条边的某一路径，那么，原连通域 1 中的每个点都可以有最短路径到这条边的顶点 i，再通过这条边，从顶点 j 有最短路径到原连通域 2 的每个点。那这其中的最大距离就是
(maxDist[i] + maxDist[j] + 边(i, j)，maxDist 是 i, j 在原来连通域中到某个点的最短路径的最大值。 - 原来的连通域有条最短路太长了，那新连通域可能还是这个直径。
因为要把新添的边枚举完，所以每个点的 maxDist 都要做，此外，还需要计算每个连通域的直径。这些可以在算该连通域的 floyd 算法后一起算掉。
由于这些点都是混的，我也只能在每一步循环里判断是不是属于某连通域了。代码拖得很长。
数据太弱
这样， Test 5 一闪而过，特别开心，可是后面的 test 又出错了。这时候数据量已经到最大了，很醉，我只能对着代码瞪眼，后来竟发现了一个非常致命的错误，取连通域直径的时候应该给 color 我却给了顶点，可这样竟然跑通了一大半的例子。
还有据 nocow 说，虽然题目说不少于两个连通域，这里给的全是两个连通域的，理解错题意都没问题。还有写错大于小于号的，都跑到了 test 7，也是真服。
精度
本来以为 float 就够了，结果遇到了啼笑皆非的问题：
> Run 7: Execution error: Your program did not produce an answer
that was judged as correct. The program stopped at 0.014 seconds;
it used 4292 KB of memory. At character number 9, your answer says
'0' while the correct answer says '2'.
Here are the respective outputs:
----- our output ---------
39796.392691
---- your output ---------
39796.390625
--------------------------
这……欺负我第一次用浮点数嘛……
我就全改成了 double，然后顺利 AC 了。
AC代码：
/*
ID:
LANG: C++
TASK: cowtour
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cfloat>
#include <cstring>
#define triangle(x, y) sqrt(pow((loc[x][0] - loc[y][0]), 2) + pow((loc[x][1] - loc[y][1]), 2))
#define max(x, y) ((x) > (y)? (x): (y))
const int maxN = 150;
int N;
bool adj[maxN][maxN]; //邻接矩阵
double dist[maxN][maxN]; //某个连通域内的最短路径
int loc[maxN][2]; //坐标
int color[maxN]; //每个点所在的连通域
double maxDist[maxN]; //每个点在该连通域据其余点的最长距离
double diameters[maxN];//颜色为i - 1的连通域的直径
void diameter(int nclr){
//仅针对连通域 nclr 的 floyd 算法
for(int k = 0; k < N; k ++){
if(color[k] != nclr) continue;
for(int i = 0; i < N; i ++){
if(color[i] != nclr) continue;
for(int j = 0; j < N; j ++){
if(color[j] != nclr) continue;
if(dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
//存maxDist, 找diameter
double dia = 0, maxd;
for(int i = 0; i < N; i ++){
if(color[i] != nclr) continue;
maxd = 0;
for(int j = 0; j < N; j ++){
if(color[j] != nclr) continue;
if(dist[i][j] > maxd) maxd = dist[i][j];
}
maxDist[i] = maxd;
if(maxd > dia) dia = maxd;
}
diameters[nclr - 1] = dia;
}
void dfs(int idx, int nclr){
if(color[idx]) return;
color[idx] = nclr;
for(int i = 0; i < N; i ++){
if(adj[idx][i]) dfs(i, nclr);
}
}
int main(){
FILE *fin = fopen("cowtour.in", "r");
FILE *fout = fopen("cowtour.out", "w");
//输入
fscanf(fin, "%d", &N);
for(int i = 0; i < N; i ++){
fscanf(fin, "%d %d\n", &(loc[i][0]), &(loc[i][1]));
}
char temp;
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
fscanf(fin, "%c", &temp);
adj[i][j] = temp - 48;
}
fscanf(fin, "%c", &temp);
}
//确定连通域
int nclr = 1;
for(int i = 0; i < N; i ++){
if(!color[i]) dfs(i, nclr ++);
}
//建立图
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(adj[i][j]){
dist[i][j] = triangle(i, j); //勾股
}else{
dist[i][j] = DBL_MAX;
}
}
dist[i][i] = 0;
}
//对各个连通域算 floyd
for(int i = 1; i < nclr; i ++){
diameter(i);
}
//不同连通域两个点连起来
double minDia = DBL_MAX, dia;
for(int i = 1; i < N; i ++){
for(int j = 0; j < N; j ++){ //i和j连接组成新的连通域
if(color[j] == color[i]) continue;
dia = max(diameters[color[i] - 1], diameters[color[j] - 1]); //可能是原连通域本身的直径
dia = max(dia, (maxDist[i] + maxDist[j] + triangle(i, j))); //可能是含有这条新边的
if(dia < minDia) minDia = dia;
}
}
fprintf(fout, "%.6f\n", minDia);
return 0;
}
性能
瞬间飞一般的效果：
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 4380 KB]
Test 2: TEST OK [0.000 secs, 4380 KB]
Test 3: TEST OK [0.000 secs, 4380 KB]
Test 4: TEST OK [0.000 secs, 4380 KB]
Test 5: TEST OK [0.000 secs, 4380 KB]
Test 6: TEST OK [0.000 secs, 4380 KB]
Test 7: TEST OK [0.014 secs, 4380 KB]
Test 8: TEST OK [0.000 secs, 4380 KB]
Test 9: TEST OK [0.000 secs, 4380 KB]
All tests OK.
Your program ('cowtour') produced all correct answers! This is your
submission #9 for this problem. Congratulations!
回顾一下，按照原来的写法，floyd 是实打实的 N ^ 3，那么150 ^ 3 = 3375000。然后，不同连通域任意两点连起来就要算一次，虽然不是 N ^ 2 次，也是这个级别的了。乖乖，150 ^ 5，逆天了，怪不得我等了两分钟。
修改之后，不同连通域连接起来就不用再算了。只是前面对于每个连通域算过一次 floyd 算法。这个当然是巨大的效果咯。
