nowcoder多校5-maximum clique 1(二分图+最大独立集)

题目链接:nowcoder多校5-maximum clique 1

题意:

给定n个互不相同的数,然后让从中选出k个数,要求这k个数的二进制表示方法中,至少有两位不一样。

题解:

考虑最大团问题和最大独立集问题的关系:原图的最大团等于其补图的最大独立集

至少有两位不一样的否命题就是恰好有一位不一样,显然,我们可以把所有的数分为两类,一类是二进制表示中1的个数为奇数,一类是二进制表示中1的个数为偶数,显然这是一个二分图,二分图的最大独立集等于总点数减去最小点覆盖数(最大匹配数)。

个人觉得主要难点是输出方案。

从集合B中没被匹配的点出发。并将其标记,表示可选,若与B中的点u相连的A中的点v,若点v没有被标记,则标记v点,表示为不可选,然后继续搜与点v匹配的B中的点u‘。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 3;
int n, m;
int a[MAXN], b[MAXN];
vector<int> edge1[MAXN], edge2[MAXN];
bool used[MAXN];
int match[MAXN], belong[MAXN];
bool dfs(int u)
{
    for (int i = 0; i < edge1[u].size(); i++)
    {
        int v = edge1[u][i];
        if (!used[v])
        {
            used[v] = 1;
            if (match[v] == 0 || dfs(match[v]))
            {
                match[v] = u;  //集合B中的v点与集合A中的u点匹配 v-u
                belong[u] = v; //集合B中的v点与集合A中的u点匹配 u-v
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int sum = 0;
    memset(match, 0, sizeof(match));
    memset(belong, 0, sizeof(belong));
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (dfs(i))
            sum++;
    }
    return sum;
}
bool vis1[MAXN], vis2[MAXN];
void dfs2(int u)
{
    vis2[u] = 1;
    for (int i = 0; i < edge2[u].size(); i++)
    {
        int v = edge2[u][i];
        if (vis1[v])
            continue;
        vis1[v] = 1;
        if (vis2[belong[v]] == 0)
            dfs2(belong[v]);
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    n = 0, m = 0;
    for (int i = 1; i <= N; i++)
    {
        int x;
        scanf("%d", &x);
        if (__builtin_popcount(x) % 2 == 0)//__builtin_popcount(x)计算x的二进制表示中1的个数
            a[++n] = x;
        else
            b[++m] = x;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (__builtin_popcount(a[i] ^ b[j]) == 1)
                edge1[i].push_back(j), edge2[j].push_back(i);
    int ans = MaxMatch();
    printf("%d\n", N - ans);
    vector<int> vec;
    vec.clear();
    for (int i = 1; i <= m; i++)
        if (match[i] == 0)
            dfs2(i);
    for (int i = 1; i <= n; i++)
        if (vis1[i] == 0)
            vec.push_back(a[i]);
    for (int i = 1; i <= m; i++)
        if (vis2[i] == 1)
            vec.push_back(b[i]);
    for (int v : vec)
        printf("%d ", v);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。