AcWing算法周赛第6场 | 3735 构造完全图

学习C++从娃娃抓起！记录下AcWing备赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：AcWing算法周赛 ｜汇总

【题目描述】

给定一个由 n n n 个点和 m m m 条边构成的无向连通图。

我们希望通过一系列操作将其变为一个完全图（即每对不同的顶点之间都恰有一条边相连）。

每次操作时，可以选择其中一个点，找到所有和它直接相连的点，使这些点两两之间连边（若两点之间已经存在边，则无需重复连接）。

请问，至少多少次操作以后，可以将整个图变为一个完全图？

【输入】

第一行包含两个整数 n , m n,m n,m。

接下来 m m m 行，每行包含两个整数 u , v u,v u,v，表示点 u u u 和点 v v v 之间存在一条边。

所有点编号 1 ∼ n 1\sim n 1∼n。

【输出】

第一行输出最少操作次数。

第二行输出每次操作所选的点的编号，整数之间空格隔开。如果最少操作次数为 0 0 0，则无需输出第二行。

如果答案不唯一，则输出任意合理方案均可。

【输入样例】

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

【输出样例】

2
2 3

【分析】

【代码详解】

《Acwing 3735 构造完全图》 #贪心# #状态压缩DP#

#include <bits/stdc++.h>
using namespace std;
const int N = 22, M = 1<<N;
typedef pair<int, int> PII;
int n, m;
int e[N];
int f[M];
PII g[M];
int main()
{
    cin >> n >> m;
    if (m == n * (n-1)/2)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i=0; i<n; i++) e[i] = 1 << i;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e[a] |= 1<<b;
        e[b] |= 1<<a;
    }
    memset(f, 0x3f, sizeof(f));
    for (int i=0; i<n; i++)
    {
        f[e[i]] = 1;
        g[e[i]] = {0, i};
    }
    for (int i=0; i< 1<<n; i++)
    {
        if (f[i] == 0x3f3f3f3f) continue;
        for (int j=0; j<n; j++)
        {
            if (i>>j & 1)
            {
                int k = i | e[j];
                if (f[k]>f[i]+1)
                {
                    f[k] = f[i] + 1;
                    g[k] = {i, j};
                }
            }
        }
    }
    int k = (1<<n) - 1;
    cout << f[k] << endl;
    while (k)
    {
        cout << g[k].second + 1 << " ";
        k = g[k].first;
    }
    return 0;
}

【运行结果】

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