时间戳

首页 > 技术文章 > 最小环问题

最小环问题

G-H-Y 2021-05-23 17:20 原文

问题定义

从一个点出发,经过一条简单路径回到起点成为环.图的最小环就是所有环中长度最小的

解决思路

在所有环中取最小值，按照集合的思路，首先对环进行分类-按照环上点的最大编号来对整个集合进行划分
Floyd算法的最外层循环恰好对更新一条线路的节点编号做出了限制，假设此时外层循环k=c(此时指刚刚结束k为c-1时的更新操作，还未进行k为c的操作)，对于一对和点(i, j)(这里我们只考虑小于c的i和j)，它们路径中间的点的编号最大可能值为c-1，一定小于c(这就是所谓的Floyd的限制)。此时最少有i和j两点，如果想得到环上最大编号为c的环，只需要让c加入。这样就构造出环上点的最大编号为c的一种情况，枚举完所有合法的i和j，就能得到环上点的最大编号为c的所有情况(即集合的一部分划分)。枚举完k的所有值，就得到了整个集合中的所有情况。期间维护一个环路径长度的最小值即为答案。细化描述见下。

Floyd算法保证了最外层循环到 \(k\) 时所有顶点间已求得以 \(0...k-1\) 为中间点的最短路径。一个环至少有 3 个顶点,设某环编号最大的顶点为 \(L\) ,在环中直接与之相连的两个顶点编号分别为 \(M\) 和 \(N\) \((M,N < L)\),则最大编号为 \(L\) 的最小环长度即为 \(Graph(M,L) + Graph(N,L) +Dist(M,N)\) ,其中 \(Dist(M,N)\) 表示以 \(0...L-1\) 号顶点为中间点时的最短路径,刚好符合 Floyd算法最外层循> 环到 \(k=L\) 时的情况,则此时对 \(M\) 和 \(N\) 循环所有编号小于 \(L\) 的顶点组合即可找到最大编号为 \(L\) 的最小环。再经过最外层 \(k\) 的循环,即可找到整个图的最小环。

这里有一个不容易理解点是\(Graph(M,L) + Graph(N,L) + Dist(M,N)\)，为什么会分为\(Graph\)和\(Dist\)，两者的区别在哪里。
想要理解这个，必须明确(M, N)和L的位置关系，上述中提到M和N与L是直接相邻的。所谓直接相邻就是M和N到L的路径上没有其它点了，所以不能使用更新后的距离，因为更新后路径上可能包含其它点。
可以容易想到更新后的路径可以使得环的长度变小，假设我们选择了更新后的路径，且设为\(M->p_1->L\)和\(N->p_2->L\)，此时和L直接相邻的点为\(p_1\)和\(p_2\)。但是和L直接相邻的点为\(p_1\)和\(p_2\)我们是可以枚举到的。
所以说我们指定M和N与L直接相邻，虽然可能获得的不是最短距离，但是我们这样做是为了枚举到所有情况的，不需要担心最优解的问题。

代码实现

/**
 * 奇妙的地方有两点：
 * 1.利用了Floyd算法的物理含义，巧妙结合集合划分，完成了不遗漏地枚举所有情况的工作
 * 2.记录路径的方法，超出了我的认知。对于路径记录我的认知还停留在必须一个点接一个点的线性存储起来，不太可能想到递归这种方式
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 110;

int n, m;
int g[N][N], d[N][N];
int p[N][N]; // p[i][j]存储更新点i和点j之间距离的点
int cnt, path[N]; // 记录路径
int res;

void get_path(int x, int y)
{
    if (p[x][y] == 0) return ; // 点x和点y之间没有中间点时就停止递归
    int k = p[x][y];
    get_path(x, k);
    path[cnt ++] = k;
    get_path(k, y);
}
int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i) g[i][i] = 0;

    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    res = 0x3f3f3f3f;
    memcpy(d, g, sizeof g);
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i < k; ++ i)
            for (int j = i + 1; j < k; ++ j)
                if ((long long)d[i][j] + g[i][k] + g[k][j] < res) // 三点之间可能不可达，出现无穷大的边，强制转化为long long
                {
                    res = d[i][j] + g[i][k] + g[k][j];
                    // 此时得到了一条更短的最小环，需要记录路径
                    cnt = 0;
                    path[cnt ++] = j;
                    path[cnt ++] = k;
                    path[cnt ++] = i;
                    get_path(i, j);
                }
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j)
                if (d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    p[i][j] = k; // 更新点i和点j距离的点是点k
                }
    }

    if (res == 0x3f3f3f3f) cout << "No solution." << endl;
    for (int i = 0; i < cnt; ++ i) cout << path[i] << ' ';

    return 0;
}

推荐阅读