PROB: cowtour

题目来自 USACO
题目翻译见 NOCOW

超时的暴搜

这道题一看也是很清楚了，求一个连通部分的直径，那就肯定是 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 算法。这个当然是巨大的效果咯。