题解：AT_abc412_d [ABC412D] Make 2-Regular Graph

jackzhangcn2013 · 2025-07-05 14:09:14 · 题解

解法

首先可以发现，每一个所有节点度数都为 2 的图一定是循环图。

循环图最小节点数为 3，故整幅图最多只能分为两个循环图。

分情况讨论。

分为单独一部分

观察到题目中的 n\leq8，可以枚举每一个可能的循环图。

由于节点数一样，我们只需要枚举所有可能的顺序，再取所有答案中的最小值即可。

分为两部分

沿用上面的思路，我们可以先枚举第一部分的大小，再将整个顺序列表分为一二两部分继续求答案即可。

代码

#include <bits/stdc++.h>
#define int long long
const int N = 100;
const int Mod = 1e9 + 7;
using namespace std;
int n, m;
bool g[N][N], tg[N][N];
inline void solve(vector<int> vec, int st, int ed)
{
    for (int i = st; i <= ed; i++)
    {
        int nxt = vec[i == ed ? st : i + 1];
        int pre = vec[i == st ? ed : i - 1];
        tg[vec[i]][nxt] = 1;
        tg[nxt][vec[i]] = 1;
        tg[vec[i]][pre] = 1;
        tg[pre][vec[i]] = 1;
    }
}
inline int get()
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cnt += tg[i][j] != g[i][j];
        }
    }
    return cnt / 2;
}
inline void clear()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            tg[i][j] = 0;
        }
    }
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    vector<int> vec;
    for (int i = 1; i <= n; i++)
    {
        vec.push_back(i);
    }
    int mi = 1e9;
    do
    {
        // 1 个圈
        clear();
        solve(vec, 0, n - 1);
        mi = min(mi, get());
        // 2 个圈
        for (int i = 3; i <= n - 3; i++)
        {
            clear();
            solve(vec, 0, i - 1);
            solve(vec, i, n - 1);
            mi = min(mi, get());
        }
    } while (next_permutation(vec.begin(), vec.end()));
    cout << mi;
    return 0;
}