maximum clique 1

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

You are given a set S containing n distinct positive integers a1,a2,…,an.

Please find a subset of S which has the maximum size while satisfying the following constraint:

The binary representations of any two numbers in this subset must have at least two different bits.

If there are multiple valid subsets, please output any one of them.

输入描述:

The input contains only two lines.

The first line contains an integer N denoting the size of S.
The second line contains N positive integers a1,a2,…,aN denoting the members of set S.

* 1≤N≤5000

* 1≤ai≤1e9

* all ai are distinct

输出描述:

You should output two lines.

The first line contains one integer m denoting the size of the subset you found.

The second line contains m positive integers denoting the member of this subset.

输入

5

3 1 4 2 5

输出

3

4 1 2

说明

3 (11₂) and 1 (01₂) has only 1 different bit so they can not be in the set together. 4 (100₂) and 1 (001₂) has 2 different bits so they can be in the set together.

Following unordered pairs are allowed to be in the set together: <1, 2>, <1, 4>, <2, 4>, <2, 5>, <3, 4>, <3, 5>. Thus the maximum set is of size 3 ({1, 2, 4}).

链接：https://ac.nowcoder.com/acm/contest/885/F?&headNav=acm
来源：牛客网

题意：在一个集合中求一个最大的子集，使得子集里任意两个数之间至少有两个二进制位不同。

思路：两个相异的数至少两个bit不一样的否命题是：恰一个bit不一样。然后考虑到A和B一个bit不一样，A和C一个bit不一样，A，B，C各不相同，那么B和C一定不会只有一个bit不一样，所以若是两个数只有一个bit不一样，我们就在它们之间连一条边，可以发现这个图是个二分图。答案就是这个二分图的最大点独立集。

#include<bits/stdc++.h>

#define N 5050

using namespace std;

typedef struct

{

    int to,next;

    long long flow;

    bool is_match;

}ss;

ss edg[*N];

int now_edge=,s,t;

int head[N];

void addedge(int u,int v)

{

    edg[now_edge]=(ss){v,head[u],};

    head[u]=now_edge++;

}

void addedge(int u,int v,long long flow)

{

   // printf("%d %d\n",u,v);

    edg[now_edge]=(ss){v,head[u],flow};

    head[u]=now_edge++;

    edg[now_edge]=(ss){u,head[v],};

    head[v]=now_edge++;

}

int dis[N];

bool bfs()

{

    memset(dis,,sizeof(dis));

    queue<int>q;

    q.push(s);

    dis[s]=;

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        for(int i=head[now];i!=-;i=edg[i].next)

        {

            ss &e=edg[i];

            if(e.flow>&&dis[e.to]==)

            {

                dis[e.to]=dis[now]+;

                q.push(e.to);

            }

        }

    }

    if(dis[t]==)return ;

    return ;

}

int current[N];

long long dfs(int x,long long maxflow)

{

    if(x==t)return maxflow;

    for(int i=current[x];i!=-;i=edg[i].next)

    {

        current[x]=i;

        ss &e=edg[i];

        if(e.flow>&&dis[e.to]==dis[x]+)

        {

            long long flow=dfs(e.to,min(maxflow,e.flow));

            if(flow!=)

            {

                e.flow-=flow;

                edg[i^].flow+=flow;

                return flow;

            }

        }

    }

    return ;

}

long long dinic()//最大流

{

    long long ans=,flow;

    while(bfs())

    {

        for(int i=;i<N;i++)current[i]=head[i];

        while(flow=dfs(s,LLONG_MAX/))ans+=flow;

    }

    return ans;

}

void init()

{

    for(int i=;i<N;i++)head[i]=-;

    now_edge=;

}

int arr[N];

int color[N]={};

void Bipartite_graph_coloring(int x,int now_color)//二分图染色

{

    if(color[x])return;

    color[x]=now_color;

    for(int i=head[x];i!=-;i=edg[i].next)Bipartite_graph_coloring(edg[i].to,now_color*-);

}

bool is_match_vertex[N]={};

int is_ans[N]={};

void dfs(int x,int type)//寻找最小点覆盖集中的点，不在该集合中的点就是最大点独立集的点

{

    if(is_ans[x])return;

    is_ans[x]=;

    for(int i=head[x];i!=-;i=edg[i].next)

    {

        int v=edg[i].to;

        if(v==s||v==t)continue;

        if(edg[i].is_match==(bool)type)dfs(v,-type);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&arr[i]);

    init();

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

    {

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

        {

            int now=arr[i]^arr[j];

            if(now==(now&-now))

            {

                addedge(i,j);

                addedge(j,i);

              //  printf("%d %d\n",arr[i],arr[j]);

            }

        }

    }

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

        if(!color[i])Bipartite_graph_coloring(i,);//先将图划分成二分图

   /* for(int i=1;i<=n;i++)if(color[i]==1)printf("%d ",arr[i]);

    printf("\n");

    for(int i=1;i<=n;i++)if(color[i]==-1)printf("%d ",arr[i]);

    printf("\n");*/

    init();

    s=n+,t=s+;

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

    {

        if(color[i]==)addedge(s,i,);

        else

            addedge(i,t,);

        if(color[i]==)

        {

            for(int j=;j<=n;j++)

            {

                int now=arr[i]^arr[j];

                if(now==(now&-now))

                {

                    addedge(i,j,);//建边准备跑二分图匹配

                }

            }

        }

    }

    int ans=n-dinic();

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

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

    {

        if(color[i]==)

        {

            for(int j=head[i];j!=-;j=edg[j].next)

            {

                if(edg[j].to!=s&&edg[j^].flow)

                {

                    edg[j].is_match=edg[j^].is_match=true;

                    is_match_vertex[i]=is_match_vertex[edg[j].to]=true;

                }

                else

                {

                    edg[j].is_match=edg[j^].is_match=false;

                }

            }

        }

    }

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

    {

        if(color[i]==-&&is_match_vertex[i]==false)

        {

            dfs(i,);

        }

    }

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

    {

        if(color[i]==&&!is_ans[i]||color[i]==-&&is_ans[i])printf("%d%c",arr[i],--ans== ? '\n': ' ');

    }

    return ;

}

巴特西

maximum clique 1

maximum clique 1

题目描述

输入描述:

输出描述:

输入

输出

说明

最新文章

热门文章