CF1927F 题解

yyrwlj · 2024-02-10 17:41:22 · 题解

题意简述

给定一个无向图，边带权，找到最小的边权最小的环，输出这个最小的边权、环上点的个数和环上每个点的编号。

思路

回顾 Kruskal 求最小生成树的过程，若当前边所连的两个点在并查集上处于同一个集合，那么连上这条边就会产生环。

我们让边权降序排序，那么最后一个出现上述情况的边就是题目中要输出边权的边。

不升序排序看第一个出现这种情况的边，是因为可能因为没连边权大的边导致当前边没出现这种情况。

输出路径 dfs 即可，设刚才求出的边所连的两点分别是 a 和 b，那么从 b 开始 dfs，直到搜到 a 为止，dfs 过程中用数组记录编号即可。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
struct Edge{
    int a, b, c;
}g[N];
int f[N];
struct EDGE{
    int to, nxt;
}G[N << 1];
int h[N], idx;
bool vis[N];
int ans[N], tot, End;
bool cmp(Edge A,Edge B)
{
    return A.c > B.c;
}
int find(int x)
{
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}
void add(int a,int b)
{
    G[++idx].to = b, G[idx].nxt = h[a], h[a] = idx;
}
bool dfs(int u,int fa)
{
    ans[++tot] = u;
    if (u == End)
    {
        printf("%d\n", tot);
        for (int i=1;i<=tot;i++)
            printf("%d ", ans[i]);
        putchar('\n');
        return true;
    }
    vis[u] = true;
    for (int i = h[u]; i; i = G[i].nxt)
    {
        int j = G[i].to;
        if (j == fa || vis[j])
            continue;
        if (dfs(j, u))
            return true;
    }
    tot --;
    return false;
}
void work()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d", &g[i].a, &g[i].b, &g[i].c);
    sort(g + 1, g + m + 1, cmp);
    for (int i=1;i<=n;i++)
        f[i] = i;
    int mn;
    for (int i=1;i<=m;i++)
    {
        int fa = find(g[i].a), fb = find(g[i].b);
        if (fa == fb)
            mn = i;
        else
            f[fa] = fb;
    }
    printf("%d ", g[mn].c);
    for (int i=1;i<=n;i++)
        h[i] = 0;
    idx = 0;
    for (int i=1;i<=m;i++)
    {
        add(g[i].a, g[i].b);
        add(g[i].b, g[i].a);
    }
    for (int i=1;i<=n;i++)
        vis[i] = false;
    int u = g[mn].a, v = g[mn].b;
    End = u;
    tot = 0;
    dfs(v, u);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}