[数据结构与算法]信息学奥赛一本通 1343：【例4-2】牛的旅行 | 洛谷 P1522 [USACO2.4] 牛的旅行 Cow Tours

【题目链接】

ybt 1343：【例4-2】牛的旅行
洛谷 P1522 [USACO2.4] 牛的旅行 Cow Tours

【题目考点】

1. 图论 最短路径 Floyd算法

Floyd算法时间复杂度： $O(V^3)$
空间复杂度：
邻接矩阵：$O(V^2)$，
邻接表：$O(V+E)$

【题目释义】

将题目抽象为图论中的概念：
牧区为顶点，牧场为连通分量，牧场的直径为连通分量中任意两顶点间最短路径长度的最大值。
题目说要在图中选择两顶点，在两顶点间连一条边，将其中两个连通分量连成一个新的连通分量，这个新的连通分量也有它的直径。
每选择两个顶点连接，为一种连接方案。每种方案都会得到一个新的连通分量的直径，求所有直径的最小值。

【解题思路】

题目中直接给了邻接矩阵，那我们也用邻接矩阵存储边信息，这样比较方便。

1. 求图中任意两顶点间的最短路径长度

题中顶点数量N最大为150，可以运行复杂度为$O(V^3)$的Floyd算法。
输入后，对整个图跑一遍Floyd算法，得到任意两点间的最短路径长度。

2. 任选两个连通分量进行连线

设该图有m个连通分量。从中任选两个连通分量A与B。确定要连接A、B两个连通分量后，设A中顶点数为na，B中顶点数为nb，A中每个顶点可以与B中每个顶点相连，一共有na*nb种连线的方案。

3. 求新的连通分量中任意两顶点间最短路径长度的最大值

对于其中一种方案，在A中的顶点va与B中的顶点vb连接一条边，这条边记为eb，连通分量A与B合并为连通分量C。边eb一定是连通分量C的桥。
思考连通分量C之中，任意两点间最短路径，可能有3类情况：

1. 子图A中两顶点间的路径，只经过A中顶点
2. 子图B中两顶点间的路径，只经过B中顶点
3. A中一个顶点到B中一个顶点，必定经过桥eb。

A中两顶点间、B中两定点间的最短路径已经通过跑Floyd算法得到了。第1、2种情况下最短路径长度的最大值都容易求。
对于第3种情况，设A中某顶点为x，B中某顶点为y，因为一定会经过桥eb，那么从x到y的最短路径一定是：x->va->vb->y。其最短路径距离为：x到va的最短路径长度+eb权值+vb到y的最短路径长度。
那么要找到A中某顶点到B中某顶点的最短路径的最大值，就是先在A中找到va最短路径长度最大的顶点x，再在B中找 到vb最短路径长度最大的顶点y，那么这样的x和y间的最短路径长度就是第3种情况下两顶点间最短路径长度的最大值。
对3种情况下的两顶点间最短路径长度的最大值取一个最大值，得到这个连通分量C的直径。

4. 得出结果

求出每种连线方案得到的新的连通分量的直径，求最小值

5. 复杂度分析

设图中顶点总数V，边数E。
首先跑Floyd算法，复杂度为$O(V^3)$
设该图有m个连通分量，分别为$g_1,g_2,...,g_m$，各连通分量顶点数分别为$n_1,n_2,...,n_m$。
对每个顶点求其与本连通分量的顶点中最短路径最长的那个顶点及路径长度。需要遍历每个连通分量，复杂度为$O({\sum }_{i=1}^m{n}_i^2)$
已知$V={\sum }_{i=1}^m{n}_i$那么$V^2=({\sum }_{i=1}^m{n}_i{)}^2\ge {\sum }_{i=1}^m{n}_i^2$。二者在一个数量级，所以可以认为该步骤的复杂度为$O(V^2)$
对每个连通分量求其中每个顶点到其它顶点最短路径长度的最大值，即可求每个连通分量的“直径”，复杂度:$O({\sum }_{i=1}^m{n}_i)=O(V)$
任选两个连通分量$g_a$与$g_b$进行连线，总连线方案数的数量级为$O(V^2)$

m个数字$n_1,n_2,...,n_m$加和为V，任取其中两个数字乘积为一种方案，求所有方案的乘积的和的数量级。
可以想象一个矩阵，有m行m列，其中第i行j列的值为$n_i?n_j$，要求的和为这个矩阵的以左上右下对角线为界右上方的部分的加和。
$?\begin{array}{ccccc}0& n_1{n}_2& n_1{n}_3& ...& n_1{n}_m\\ n_2{n}_1& 0& n_2{n}_3& ...& n_2{n}_m\\ n_3{n}_1& n_3{n}_2& 0& ...& n_3{n}_m\\ ...& ...& ...& ...& ...\\ n_m{n}_1& n_m{n}_2& n_m{n}_3& ...& 0\end{array}?$
显然这个矩阵是对称的，所以我们可以求出这个矩阵中所有元素的和，再除以2，也可以得到结果
该矩阵第i行的加和为$n_i(V?n_i)$
全部加和为${\sum }_{i=1}^m{n}_i(V?n_i)={\sum }_{i=1}^m{n}_{i}V?{\sum }_{i=1}^m{n}_i^2=V^2?{\sum }_{i=1}^m{n}_i^2\le V^2$
乘积的加和不会大于$\frac{V^2}{2}$，所以可以认为总连线方案数的数量级为$O(V^2)$

针对每种连线方案，求新连通分量的直径，就是上面第3点中的3种情况，前两种情况的值已经求出，第三种情况只需要做简单加和计算就能求出。这一步操作复杂度为$O(1)$
综上，该算法的时间复杂度为$O(V^3)+O(V^2)+O(V)+O(V^2)?O(1)=O(V^3)$

【题解代码】

解法1：用vector数组存储各个连通分量

#include<bits/stdc++.h>
using namespace std;
#define N 200
#define MAXDOUB 1e9
struct Cord
{
    int x, y;
};
Cord cord[N];
bool edge[N][N];//邻接矩阵 
vector<int> conn[N];//conn[i]:第i个连通分量，里面保存了这个连通分量中的各个顶点
int n, cn;//n:顶点数 cn连通分量的个数，conn的数量 
bool vis[N];
double dis[N][N];
int dv[N];//dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点
double mxDis[N];//mxDis[i]:第i个连通分量中两点间最长的最短路径长度 
double ans = MAXDOUB; 
double getDis(Cord &a, Cord &b)//两点间距离 
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} 
void initGraph()
{
    char c;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> cord[i].x >> cord[i].y;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            cin >> c;
            edge[i][j] = c - '0';//如果c为'0'，edge[i][j]为0，如果c为'1'，edge[i][j]为1 
        }
}
void dfs(int v)
{
    for(int i = 1; i <= n; ++i)
    {
        if(edge[v][i] && vis[i] == false)
        {
            vis[i] = true;
            conn[cn].push_back(i);
            dfs(i);
        }
    }
}
void initConn()//初始化连通分量vector数组 
{//类似解连通块问题 
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i] == false)
        {
            vis[i] = true;
            conn[++cn].push_back(i);//conn从下标1开始存
            dfs(i);
        }
    }
}
void floyd()
{
    memset(dis, 0x43, sizeof(dis));//将dis各元素设为无穷大 
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                dis[i][j] = 0;
            else if(edge[i][j])
                dis[i][j] = getDis(cord[i], cord[j]);
        }
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}
void initDv()//初始化dv和mxDis。dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点 
{
    for(int k = 1; k <= cn; ++k)//遍历每个连通分量 
    {
        for(int i = 0; i < conn[k].size(); ++i)
        {
            double mx = -1;//u到本连通分量中的另一个顶点最短路径中的最大值 
            int u = conn[k][i];
            for(int j = 0; j < conn[k].size(); ++j)
            {
                int v = conn[k][j];
                if(mx < dis[u][v])
                {
                    mx = dis[u][v];
                    dv[u] = v;
                }
            }
            mxDis[k] = max(mxDis[k], mx); 
        }
    }
}
int main()
{
    initGraph();
    initConn();
    floyd();
    initDv();
    for(int a = 1; a <= cn; ++a)//遍历每对连通分量 
        for(int b = a + 1; b <= cn; ++b)
        {
            for(int i = 0; i < conn[a].size(); ++i)
                for(int j = 0; j < conn[b].size(); ++j)
                {
                    int u = conn[a][i], v = conn[b][j];//选择a连通分量中的u与b连通分量中的v进行连线 
                    double x = dis[u][dv[u]] + dis[v][dv[v]] + getDis(cord[u], cord[v]);//从a中某顶点到b中某顶点的最短路径 
                    double d = max(max(mxDis[a], mxDis[b]), x);//将a与b连接后得到的新连通分量的直径 
                    ans = min(ans, d);//结果为新连通分量直径的最小值 
                }
        }
    cout << fixed << setprecision(6) << ans;
    return 0; 
}

解法2：用conn[i]表示顶点i所在的连通分量

#include<bits/stdc++.h>
using namespace std;
#define N 200
#define INF 1e9
struct Cord
{
    int x, y;
};
Cord cord[N];
bool edge[N][N];//邻接矩阵 
int n, cn;//n:顶点数 cn连通分量的个数，conn的数量 
bool vis[N];
double dis[N][N];
int dv[N];//dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点
double mxDis[N];//mxDis[i]:第i个连通分量中两点间最长的最短路径长度
int conn[N];//conn[i]:顶点i所属的连通分量编号 
double ans = INF; 
double getDis(Cord &a, Cord &b)//两点间距离 
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} 
void initGraph()
{
    char c;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> cord[i].x >> cord[i].y;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            cin >> c;
            edge[i][j] = c - '0';//如果c为'0'，edge[i][j]为0，如果c为'1'，edge[i][j]为1 
        }
}
void dfs(int v)
{
    for(int i = 1; i <= n; ++i)
    {
        if(edge[v][i] && vis[i] == false)
        {
            vis[i] = true;
            conn[i] = cn;
            dfs(i);
        }
    }
}
void initConn()
{
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i] == false)
        {
            vis[i] = true;
            conn[i] = ++cn;
            dfs(i);
        }
    }
}
void floyd()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                dis[i][j] = 0;
            else if(edge[i][j])
                dis[i][j] = getDis(cord[i], cord[j]);
            else
                dis[i][j] = INF;
        }
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}
void initDv()//初始化dv和mxDis。dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点 
{
    for(int i = 1; i <= n; ++i)
    {
        double mx = -1;
        for(int j = 1; j <= n; ++j)
        {
            if(conn[i] == conn[j] && mx < dis[i][j])
            {
                mx = dis[i][j];
                dv[i] = j;
            }
        }
        mxDis[conn[i]] = max(mxDis[conn[i]], mx); //mxDis[i]:第i个连通分量中两点间最长的最短路径长度
    }
}
int main()
{
    double x, d;
    initGraph();
    initConn();
    floyd();
    initDv();
    for(int i = 1; i <= n; ++i)//从i到j连线 
        for(int j = 1; j <= n; ++j)
        {
            if(conn[i] != conn[j])
            {
                x = dis[i][dv[i]] + dis[j][dv[j]] + getDis(cord[i], cord[j]);//从i所在连通分量中某顶点到j所在连通分量中某顶点的最短路径 
                d = max(max(mxDis[conn[i]], mxDis[conn[j]]), x);//将i与j连接后得到的新连通分量的直径 
                ans = min(ans, d);//结果为新连通分量直径的最小值 
            }
        }
    cout << fixed << setprecision(6) << ans;
    return 0; 
}

解法3：用并查集表示顶点所在的连通分量

初始状态下每个顶点是一个集合，每有一条边，就把这条边连接的两个顶点所在的集合合并。最后每个集合表示一个连通分量。

#include<bits/stdc++.h>
using namespace std;
#define N 200
#define INF 1e9
struct Cord
{
    int x, y;
};
Cord cord[N];
bool edge[N][N];//邻接矩阵 
int n, cn;//n:顶点数 cn连通分量的个数，conn的数量 
bool vis[N];
double dis[N][N];
int dv[N];//dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点
double mxDis[N];//mxDis[i]:第i个连通分量中两点间最长的最短路径长度
double ans = INF; 
int fa[N];
void initFa()
{
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y)
{
    fa[find(x)] = find(y);
}
double getDis(Cord &a, Cord &b)//两点间距离 
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} 
void initGraph()
{
    char c;
    cin >> n;
    initFa();
    for(int i = 1; i <= n; ++i)
        cin >> cord[i].x >> cord[i].y;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            cin >> c;
            edge[i][j] = c - '0';//如果c为'0'，edge[i][j]为0，如果c为'1'，edge[i][j]为1
            if(edge[i][j])
                merge(i, j);
        }
}
void floyd()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                dis[i][j] = 0;
            else if(edge[i][j])
                dis[i][j] = getDis(cord[i], cord[j]);
            else
                dis[i][j] = INF;
        }
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}
void initDv()//初始化dv和mxDis。dv[i]:与顶点i在同一连通分量中的 到顶点i最短路径最长的顶点 
{
    for(int i = 1; i <= n; ++i)
    {
        double mx = -1;
        for(int j = 1; j <= n; ++j)
        {
            if(find(i) == find(j) && mx < dis[i][j])
            {
                mx = dis[i][j];
                dv[i] = j;
            }
        }
        mxDis[find(i)] = max(mxDis[find(i)], mx); //mxDis[i]:第i个连通分量中两点间最长的最短路径长度
    }
}
int main()
{
    double x, d;
    initGraph();
    floyd();
    initDv();
    for(int i = 1; i <= n; ++i)//从i到j连线 
        for(int j = 1; j <= n; ++j)
        {
            if(find(i) != find(j))
            {
                x = dis[i][dv[i]] + dis[j][dv[j]] + getDis(cord[i], cord[j]);//从i所在连通分量中某顶点到j所在连通分量中某顶点的最短路径 
                d = max(max(mxDis[find(i)], mxDis[find(j)]), x);//将i与j连接后得到的新连通分量的直径 
                ans = min(ans, d);//结果为新连通分量直径的最小值 
            }
        }
    cout << fixed << setprecision(6) << ans;
    return 0; 
}