independent set 1

发布时间：2020-12-15 05:30:51 所属栏目：Java 来源：网络整理

导读：?independent set 1 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 102400K，其他语言204800K 64bit IO Format: %lld 题目描述 Note:? For C++ languages,the memory limit is 100 MB.? For other languages,the memory limit is 200 MB. In graph theo

?independent set 1

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 102400K，其他语言204800K
64bit IO Format: %lld

题目描述

Note:? For C++ languages,the memory limit is 100 MB.?For other languages,the memory limit is 200 MB.

In graph theory,an independent set is a set of nonadjacent vertices in a graph. Moreover,an independent set is maximum if it has the maximum cardinality (in this case,the number of vertices) across all independent sets in a graph.

An induced subgraph G‘(V‘,E‘) of a graph G(V,E) is a graph that satisfies:

*

2^n?possible induced subgraphs of the given graph. Please calculate the sum of the 2^n?such cardinalities.

输入描述:

The first line contains two integers n and m (

输出描述:

Print one line,containing one integer represents the answer.

输入

3 2
0 1
0 2

输出

说明

The cardinalities of the maximum independent set of every subset of vertices are: {}: 0,{0}: 1,{1}: 1,{2}: 1,{0,1}: 1,2}: 1,{1,2}: 2,1,2}: 2. So the sum of them are 9.
链接：https://ac.nowcoder.com/acm/contest/885/E
来源：牛客网

题意：求一个图的2^n种子图的最大点独立集。
思路：

??我们可以用一个 n-bit 2 进制整数来表示一个点集，第 i 个 bit 是 1 就代表点集包含第 i 个点，若是 0 则不包含?
?? 每个点相邻的点也可以用一个 n-bit 2 进制整数表示，计做 ci，若第 i 个点和第 j 个点相邻， ci 的第 j 个 bit 是 1，否则是 0
?? 记 x 的最低位且是 1 的 bit 的位置是 lbx
?? 令 dp[x] 代表点集 x 的最大独立集 size，那么我们能够根据点 lbx 是否属于最大独立集来列出以下关系式：
?dp[x] = max(dp[x - (1<<lbx)],dp[x & (~clb_x)] + 1) (使用 c 语言运算符)

??高效位运算参考博客：https://blog.csdn.net/yuer158462008/article/details/46383635

#include<bits/stdc++.h>
using namespace std;
char dp[1<<26];
int Map[26]={0};
int max(char a,int b)
{
    if(a>b)return a;
    return b;
}
int main()
{    
    int n,m;
    scanf("%d %d",&n,&m);
    
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        Map[u]|=(1<<v);
        Map[v]|=(1<<u);
    }
    for(int i=0;i<n;i++)Map[i]|=1<<i;
    
    int upper=1<<n;
    long long ans=0;
    for(int i=1;i<upper;i++)
    {
        int lbx=__builtin_ctz(i);
        dp[i] = max(dp[i - (1<<lbx)],dp[i & (~Map[lbx])] + 1);
        ans+=dp[i];
    }
    printf("%lldn",ans);
    return 0;
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!