maximum clique 1
发布时间:2020-12-15 05:30:11 所属栏目:Java 来源:网络整理
导读: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 w
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. 输出描述:You should output two lines. 输入5 3 1 4 2 5 输出3 4 1 2 说明
3 (11
2) and 1 (01
2) has only 1 different bit so they can not be in the set together. 4 (100
2) and 1 (001
2) 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,5>,<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[64*N]; int now_edge=0,s,t; int head[N]; void addedge(int u,int v) { edg[now_edge]=(ss){v,head[u],0}; head[u]=now_edge++; } void addedge(int u,int v,long long flow) { // printf("%d %dn",u,v); edg[now_edge]=(ss){v,flow}; head[u]=now_edge++; edg[now_edge]=(ss){u,head[v],0}; head[v]=now_edge++; } int dis[N]; bool bfs() { memset(dis,0,sizeof(dis)); queue<int>q; q.push(s); dis[s]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edg[i].next) { ss &e=edg[i]; if(e.flow>0&&dis[e.to]==0) { dis[e.to]=dis[now]+1; q.push(e.to); } } } if(dis[t]==0)return 0; return 1; } int current[N]; long long dfs(int x,long long maxflow) { if(x==t)return maxflow; for(int i=current[x];i!=-1;i=edg[i].next) { current[x]=i; ss &e=edg[i]; if(e.flow>0&&dis[e.to]==dis[x]+1) { long long flow=dfs(e.to,min(maxflow,e.flow)); if(flow!=0) { e.flow-=flow; edg[i^1].flow+=flow; return flow; } } } return 0; } long long dinic()//最大流 { long long ans=0,flow; while(bfs()) { for(int i=0;i<N;i++)current[i]=head[i]; while(flow=dfs(s,LLONG_MAX/2))ans+=flow; } return ans; } void init() { for(int i=0;i<N;i++)head[i]=-1; now_edge=0; } int arr[N]; int color[N]={0}; void Bipartite_graph_coloring(int x,int now_color)//二分图染色 { if(color[x])return; color[x]=now_color; for(int i=head[x];i!=-1;i=edg[i].next)Bipartite_graph_coloring(edg[i].to,now_color*-1); } bool is_match_vertex[N]={0}; int is_ans[N]={0}; void dfs(int x,int type)//寻找最小点覆盖集中的点,不在该集合中的点就是最大点独立集的点 { if(is_ans[x])return; is_ans[x]=1; for(int i=head[x];i!=-1;i=edg[i].next) { int v=edg[i].to; if(v==s||v==t)continue; if(edg[i].is_match==(bool)type)dfs(v,1-type); } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&arr[i]); init(); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int now=arr[i]^arr[j]; if(now==(now&-now)) { addedge(i,j); addedge(j,i); // printf("%d %dn",arr[i],arr[j]); } } } for(int i=1;i<=n;i++) if(!color[i])Bipartite_graph_coloring(i,1);//先将图划分成二分图 /* 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+1,t=s+1; for(int i=1;i<=n;i++) { if(color[i]==1)addedge(s,i,1); else addedge(i,t,1); if(color[i]==1) { for(int j=1;j<=n;j++) { int now=arr[i]^arr[j]; if(now==(now&-now)) { addedge(i,j,1);//建边准备跑二分图匹配 } } } } int ans=n-dinic(); printf("%dn",ans); for(int i=1;i<=n;i++) { if(color[i]==1) { for(int j=head[i];j!=-1;j=edg[j].next) { if(edg[j].to!=s&&edg[j^1].flow) { edg[j].is_match=edg[j^1].is_match=true; is_match_vertex[i]=is_match_vertex[edg[j].to]=true; } else { edg[j].is_match=edg[j^1].is_match=false; } } } } for(int i=1;i<=n;i++) { if(color[i]==-1&&is_match_vertex[i]==false) { dfs(i,0); } } for(int i=1;i<=n;i++) { if(color[i]==1&&!is_ans[i]||color[i]==-1&&is_ans[i])printf("%d%c",--ans==0 ? ‘n‘: ‘ ‘); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |