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

· · 题解

题目简述

给你一张顶点编号为 1\sim N 且有 M 条边的简单无向图，求让这个图的每个顶点的度数均恰好为 2，需要添加或删除一条边的最少次数。

主要思路

不难发现，想要使每个顶点的度数均为 2，那么这个图一定是一个环，并且对于 3\le N\le8 的数据，就可以直接进行时间复杂度为 O(N!) 的搜索枚举这个环中顶点排列的顺序。

虽然这个枚举中会有因为是环而重复的情况（例如 1 2 3 4 和 2 3 4 1），但 8!\approx 4\times 10^{4} 也就没有那个必要去优化了。

枚举出一种排列后，计算需要添加或删除一条边的最少次数时，可以先计算出需要添加几条边，那么边的存储就可以使用邻接矩阵而方便计算，假设排列为 a_{1}\sim a_{n}，需要添加的边数即给定的边中不存在 a_{1}\sim a_{2},a_{2}\sim a_{3},\cdots,a_{n}\sim a_{1} 的边的边数，假设为 k，那么需要删除的边数即 m+k-n，n 就是最终需要剩下几条边。

于是就可以写下以下搜索代码：

// use 表示排列，vis 表示是否已经出现在排列中
void dfs(int u) {
    if (u > n) {
        int res = 0;
        for (int i = 1; i <= n; i++) res += !edge[use[i]][use[i % n + 1]];
        res += m + res - n;
        res += m + res - n;
        ans = min(ans, res);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        use[u] = i;
        vis[i] = true;
        dfs(u + 1);
        vis[i] = false;
    }
}

随后你就会发现过不了样例#3，并且如果你按刚才的思路来算根本就得不到正确答案 2。

因为题目中只要求了每个顶点的度数为 2，但实际可以有多个环，这样每个顶点的度数也为 2，且总边数也为 n。

由于一个要使每个顶点的环的顶点数要 \ge 3，对于 N \le 8 这张图最多能有 2 个环，所以只需要在计算一个大环需要添加或删除的边数后再枚举两个环中的一个环的起始点与长度，另外一个环也就有了，随后再计算第一个环需要添加或删除的边数加第二个环需要添加或删除的边数的和即可。

注意事项

在枚举第一个环时起始点加长度不是一定要 \le n，因为这是一个环，假设排列为 1 3 5 2 4 那么 2 4 1 也是一个环。

AC Code

#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
template<typename T> void read(T &x) { int f = 1; x = 0; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }x *= f; }
template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
template<typename T> void print(T x) { if (x < 0) { putchar('-'); x = -x; }if (x > 9) { print(x / 10); }putchar(char(x % 10 + 48)); }
template<typename T, typename ...Args> void print(T x, Args ...args) { print(x); putchar(' '); print(args...); }

typedef long long ll;
typedef long double db;
const int N = 8 + 10;
const int INT_INF = 0x3f3f3f3f;
// ----------------------------

// ----------------------------
bool vis[N], edge[N][N];
int n, m, ans = INT_INF, use[N];
// ----------------------------
void dfs(int u) {
    if (u > n) {
        int res = 0;
        for (int i = 1; i <= n; i++) res += !edge[use[i]][use[i % n + 1]];
        res += m + res - n;
        ans = min(ans, res);
        int r;
        for (int len = 3; len <= n - 3; len++) {
            for (int l = 1; l <= n; l++) {
                res = 0;
                if (l <= n - len + 1) r = l + len - 1;
                else r = (l + len) % n - 1;
                for (int i = l; i != r % n + 1; i = i % n + 1) {
                    if (i != r) res += !edge[use[i]][use[i % n + 1]];
                    else res += !edge[use[i]][use[l]];
                }
                for (int i = r % n + 1; i != l; i = i % n + 1) {
                    if (i != (l + n - 2) % n + 1) res += !edge[use[i]][use[i % n + 1]];
                    else res += !edge[use[i]][use[r % n + 1]];
                }
                res += m + res - n;
                ans = min(ans, res);
            }

        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        use[u] = i;
        vis[i] = true;
        dfs(u + 1);
        vis[i] = false;
    }
}

int main() {
    int u, v; read(n, m);
    for (int i = 1; i <= m; i++) {
        read(u, v);
        edge[u][v] = edge[v][u] = true;
    }
    // ----------------------------
    dfs(1);
    // ----------------------------
    print(ans);
    return 0;
}