Floyd 算法求最小环

算法思路

  • DP思路
    • 状态表示：化整为零：按照环上的最大点的编号来分类，可保证不重不漏
    • 状态计算：枚举和最大点相邻的两点i,j同时使得dist[i][j]距离最小，即可保证最小环i->k->j->i的权值最小
  • 证明算法步骤2的正确性：
    • 若枚举到最大点k时，按照如上所述的方法找到最小环上的一个点大于k看，假设为k+2，则我们在该点k处用所有小于k的点i,j找到的最小环，一定不是全局的最优解，当我们枚举到 k+2 时，方可枚举到全局最小换，反证成立，则算法成立

具体实现

  • 每次floyd更新最外层的k时，已知的路径中，只含0~k-1这些点更新的路径，如此可求得环上的最大值为k时的最小环。
  • 求最小环权值：枚举与k相邻的i,j(小于k)，使dist[i][j]最小，即为环上最大点为k的最小环的权值，依次更新k直到k等于n，算法结束
  • 求最小环路径：记录pos[i][j]为 [i, j] 区间，是由pos[i][j]更新而来，每次更新答案，递归求解路径

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], g[N][N];
int path[N], pos[N][N];
int cnt;

void get_path(int l, int r)
{
    int k = pos[l][r];
    if (k == 0) return;
    
    get_path(l, k);
    path[cnt ++ ] = k;
    get_path(k, r);
}

int main()
{
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    memcpy(d, g, sizeof g);
    
    int res = INF;
    for (int k = 1; k <= n; k ++ )
    {
        for (int i = 1; i < k; i ++ )
            for (int j = i + 1; j < k; j ++ )
                if ((LL)d[i][j] + g[j][k] + g[k][i] < res) // i->k->j
                {
                    res = d[i][j] + g[j][k] + g[k][i];
                    cnt = 0;
                    path[cnt ++ ] = k;
                    path[cnt ++ ] = i;
                    get_path(i, j);
                    path[cnt ++ ] = 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];
                    pos[i][j] = k;
                }
    }
    
    if (res == INF) puts("No solution.");
    else 
    {
        for (int i = 0; i < cnt; i ++ )
            printf("%d ", path[i]);
        puts("");
    }
    
    return 0;
}