Codeforces #454 div1 C party（状态压缩bfs）

题意：

给你N个点的一幅图,初始图中有M条边,每次操作可以使得一个点连接的所有点变成一个团,问你最少多少次操作可以使得整个图变成一个团.

解法：

因为N很小所以我们可以二进制压缩来表示一个点与其他点之间的关系。二进制的第i位代表标号位i+1的人。例如标号为1的人认识标号为3与5还有7的人，标号为1的二进制压缩结果就为0000000000000000001010101(标号为i的人肯定认识他自身)。

//https://www.cnblogs.com/FxxL/p/8095418.html

#include <iostream>

#include <string.h>

#include <cmath>

#include <algorithm>

#include <cstdio>

#include <queue>

using namespace std;

const int maxn = (1 << 22), maxm = 30;

int n, m;

int dp[maxn + 50], key[maxn + 50], str[maxn + 50];

int a[maxm], num;

queue<int> q;

void bfs()

{

    int now, tmp;

    while (!q.empty())

    {

        now = q.front(); q.pop();

        if (now == ((1 << n) - 1))

            return;

        for (int i = 0; i < n; i++) {

            if (now&(1 << i)) {//当前的数的第i位是1，也就是朋友i可以做介绍

                tmp = now | a[i];

                if (dp[tmp] == 0) {//出现的是没有记录过的数

                    dp[tmp] = dp[now] + 1;

                    key[tmp] = i;//记录更新到tmp的状态是通过i做介绍得来的

                    str[tmp] = now;//记录tmp的是now通过i做介绍得来的，用来记录路径。

                    q.push(tmp);

                }

            }

        }

    }

}

int main()

{

    int x, y, tmp;

    scanf("%d%d", &n, &m);//n个人

    memset(a, 0, sizeof(a));

    memset(dp, 0, sizeof(dp));

    memset(key, -1, sizeof(key));

    memset(str, -1, sizeof(str));

    for (int i = 0; i < n; i++) {

        a[i] |= (1 << i);//第i个人肯定认识他自己

    }

    for (int i = 1; i <= m; i++)

    {

        scanf("%d%d", &x, &y);

        x--, y--;

        a[x] |= (1 << y);   //更新每个人与其他人的关系，如果认识就给那一位的人标为1

        a[y] |= (1 << x);

    }

    for (int i = 0; i<n; i++)

    {

        dp[a[i]] = 1;

        key[a[i]] = i;

        q.push(a[i]);

    }

    if (m == n*(n - 1) / 2)

    {

        printf("0\n");

        return 0;

    }

    bfs();

    tmp = (1 << n) - 1;

    //回溯求解

    while (tmp != -1)

    {

        ++num;

        tmp = str[tmp];

    }

    printf("%d\n", num);

    return 0;

}

巴特西

Codeforces #454 div1 C party（状态压缩bfs）

最新文章

热门文章