题目描述

https://www.acwing.com/problem/content/1395/

算法1

(并查集 + floyd) $O(n^3)$

该题是一道求无向图的最小环问题，可以用floyd算法计算每个点之间的最短路径，然后用来更新最小环
由于该题只给出了边的编号，并且边与边之间有重合的点，所以使用并查集将重合的点合并，就可以正常
求解了

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f; //点的数量是边的两倍
typedef long long LL;

struct Edge{
    int w;
    vector<int> e[2]; //0 是指该边左边的边的编号，1是指右边的边的编号
}edge[N];
int n;
int p[2 * N];
int d[N][N], g[N][N];

int get(int a, int b)
{
    for(int j = 0; j < 2; j ++)  //枚举该边左右两边
        for(int k: edge[b].e[j])
            if(a == k)  //如果两条边相连，则返回该边重合的点的编号
                return b + j * n;  
    return -1;
}

int find(int x)  //并查集模板
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    //输入数据
    for(int k = 0; k < n; k ++)
    {
        int i;
        scanf("%d", &i);
        int s, cnt1, cnt2;
        scanf("%d%d%d", &edge[i].w, &cnt1, &cnt2);
        while(cnt1 --)
        {
            int id;
            scanf("%d", &id);
            edge[i].e[0].push_back(id);
        }
        while(cnt2 --)
        {
            int id;
            scanf("%d", &id);
            edge[i].e[1].push_back(id);
        }
    }

    for(int i = 1; i <= 2 * n; i ++) p[i] = i;
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < 2; j ++)
            for(int k: edge[i].e[j])
            {
                int a = i + j * n, b = get(i, k); 
                //一条边的左边的点编号是1 - n, 右边的点的编号是n - 2n
                // a表示一条边的某个端点编号，b表示该边所连的另一条的边与该边重合的点的编号，将他们合并
                p[find(a)] = find(b);
            }

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

        int a = find(i), b = find(i + n);  //因为前面规定一条边两点之差为n，因为会有重点，这里要用并查集防止
        g[a][b] = g[b][a] = edge[i].w;
    }

    memcpy(d, g, sizeof d); //拷贝一份原图
    //floyd求无向图的最小环
    LL res = INF;
    for(int k = 1; k <= 2 * n; k ++)  //图的方向 i -> k -> j -> i
    {
        for(int i = 1; i < k; i ++)
            for(int j = i + 1; j < k; j ++)
               res = min((LL)res, d[i][j] + (LL)g[j][k] + g[k][i]); //更新环

        for(int i = 1; i <= n * 2; i ++)
            for(int j = 1; j <= n * 2; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  //更新i，j之间的最短路
    }
    cout << res << endl;
    return 0;
}