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

· · 题解

题目意思

题目就是给你一个简单图，你可以重复以下两种操作：

  1. 添加一条无向边。
  2. 删除一条无向边。

求把图中任意一点都变成度数为 2 的最少操作。

思路

因为 n \le 8，很小，所以考虑 dfs 爆搜。

每次我们 dfs 时传进一个参数，记作 x，表示枚举到了第 x 个点。

然后，我们分为三种情况。

  1. 编号为 x 的点的度数为 2，这时不用操作，直接 dfs 枚举 x + 1。
  2. 标号为 x 的点的度数为 1，这时我们枚举编号为 x + 1 到 n 的点，找到度数不为 2 的点，然后修改一下图，连接两个点，再 dfs 下去，记得回溯。
  3. 编号为 x 的点的度数大于 2，我们照样枚举，只不过这次要枚举两个点，保证两个点不相同且大于 x，这时，如果两个点的度数都不为 2，则像操作 2 一样修改图，再 dfs 下去。

总时间复杂度：O(2 ^ n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,g[100],h[100][100],t1,ans = INT_MAX;
struct Info {
    int u,v;
} e[100];
inline void dfs(int x){
    if (x == n + 1){
        int g1 = 0,h1 = 0;
        for (int i = 1;i <= t1;i++) if (h[e[i].u][e[i].v]) g1++; else h1++;
        ans = min(ans,h1 + m - g1);
        return;
    }
    if (g[x] == 2) dfs(x + 1);
    else if (g[x] == 1){
        for (int i = x + 1;i <= n;i++)
            if (g[i] != 2) g[x]++,g[i]++,t1++,e[t1].u = x,e[t1].v = i,dfs(x + 1),t1--,g[x]--,g[i]--;
    } else {
        for (int i = x + 1;i <= n;i++)
            if (g[i] != 2)
                for (int j = i + 1;j <= n;j++)
                    if (g[j] != 2) g[x] += 2,g[i]++,g[j]++,t1++,e[t1].u = x,e[t1].v = i,t1++,e[t1].u = x,e[t1].v = j,dfs(x + 1),t1 -= 2,g[x] -= 2,g[i]--,g[j]--;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1,x,y;i <= m;i++){
        scanf("%d%d",&x,&y);
        if (x > y) swap(x,y);
        h[x][y] = 1;
    }
    dfs(1),printf("%d\n",ans);
}