题目详情题解（0）讨论（0）提交记录（0）

AT_abc412_d.[ABC412D] Make 2-Regular Graph

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 NN 个顶点、MM 条边的简单无向图 GG。顶点编号为 1,2,…,N1, 2, \ldots, N，第 ii 条边连接顶点 AiA_i 和顶点 BiB_i。

你可以按任意顺序、任意次数重复以下两种操作：

  • 向 GG 中添加一条无向边。
  • 从 GG 中删除一条无向边。

请你求出，将 GG 变为所有顶点的度数都为 22 的简单无向图所需操作次数的最小值。

简单无向图指的是没有自环和重边的无向图。

输入格式

输入按以下格式从标准输入读入。

NN MM
A1A_1 B1B_1
⋮\vdots
AMA_M BMB_M

输出格式

请输出答案。

输入输出样例

  • 输入#1

    5 4
1 2
1 5
2 4
4 5

    输出#1

    3

  • 输入#2

    3 0

    输出#2

    3

  • 输入#3

    6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

    输出#3

    2

  • 输入#4

    8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

    输出#4

    13

说明/提示

限制条件

  • 3≤N≤83 \leq N \leq 8
  • 0≤M≤N(N−1)20 \leq M \leq \frac{N(N-1)}{2}
  • 输入给出的图 GG 是简单无向图
  • 输入的所有数值均为整数

样例解释 1

例如，可以通过如下方式，在 33 次操作内将 GG 变为所有顶点度数为 22 的简单无向图：

  • 添加一条连接顶点 22 和顶点 33 的边。
  • 删除一条连接顶点 22 和顶点 44 的边。
  • 添加一条连接顶点 33 和顶点 44 的边。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页