欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU Bit Magic (2-Sat)

程序员文章站 2022-06-02 17:30:30
...
  • Bit Magic
  • 题意
    已知一位数组a[]和二维数组b[][]满足以下关系
    HDU Bit Magic (2-Sat)
    给定数组b[][],问是否存在数组a[],如果存在,输出"YES",否则输出"NO"
    • 题解
      写的是2-Sat的专题,想了好久都没想到怎么和2-Sat扯上关系,后来看了题解,说是按位进行2-Sat,就知道要怎么做了。因为位数最多不超过31位i,我一开始想的是从数组b[][]中找到条件,对这31位综合起来只进行一次2-Sat,后来T掉了,但是想了想复杂度是不会T的,现在还想不明白。后来只好对每一位建图,对每一位进行一次2-Sat,如果有一位找出了矛盾,就直接NO了。
    • 代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair<ll,ll> pa;
const int dir_4[4][2]={-1,0,0,1,1,0,0,-1};
const int dir_8[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAX_N=520*2;
struct node{
	int to,nex;
}edge[1000000];
int N,cnt,tot,scc_cnt,head[MAX_N],dfn[MAX_N],low[MAX_N],sccnum[MAX_N];
int base;
ll  b[520][520];
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].nex=head[u];
	head[u]=cnt++;
	return ;
}
stack<int>st;
void Init(){
	cnt=tot=scc_cnt=0;
	for(int i=0;i<N*2;i++){
		head[i]=-1;
		dfn[i]=sccnum[i]=0;
	}
	while(!st.empty())
	st.pop();
	return ;
}
void built_map(int k){
	int i,j;
	for(i=0;i<N-1;i++){
		for(j=i+1;j<N;j++){
			int x=2*i;
			int y=2*j;				
			if(b[i][j]&(1ll<<k)){//第k位是1 
				if(i%2==1&&j%2==1){// 或操作 
					add(x,y^1);
					add(y,x^1);
				}
				else if(i%2==0&&j%2==0){// 与操作 
					add(x^1,y^1);
					add(y^1,x^1);
				}
				else{// 异或操作 
					add(x,y^1);
					add(x^1,y);
					add(y,x^1);
					add(y^1,x);
				}					 
			}
			else{//第k位是0 
				if(i%2==1&&j%2==1){// 或操作 
					add(x,y);
					add(y,x);
				}
				else if(i%2==0&&j%2==0){// 与操作 
					add(x^1,y);
					add(y^1,x);
				}
				else{// 异或操作 
					add(x,y);
					add(y,x);
					add(x^1,y^1);
					add(y^1,x^1);
				}					
			}
		}
	}
	return ;
}
void Tarjan(int u){
	dfn[u]=low[u]=++tot;
	st.push(u);
	int i,j,v;
	for(i=head[u];~i;i=edge[i].nex){
		v=edge[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccnum[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++scc_cnt;
		while(!st.empty()){
			v=st.top();
			st.pop();
			sccnum[v]=scc_cnt;
			if(u==v)
			break;
		}
	}
	return ;
}
bool is_ok(){
	int i,j,k;
	for(k=0;k<31;k++){//枚举每一位是否有矛盾 
		Init();
		built_map(k);
		for(i=0;i<N*2;i++){
			if(!dfn[i])
			Tarjan(i);
		}
		for(i=0;i<N*2;i+=2){
			if(sccnum[i]==sccnum[i^1])
			return false;
		}			
	}
	return true;
}
bool is_pre(){
	int i,j,k;
	for(i=0;i<N;i++){ 
		for(j=i;j<N;j++){
			if(i==j&&b[i][j]!=0)
			return false;
			if(b[i][j]!=b[j][i])
			return false;
		}
	}
	return true;
}
int main()
{
//  freopen(".../.txt","w",stdout);
//  freopen(".../.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int i,j,k;
	while(~scf("%d",&N)){
		for(i=0;i<N;i++){
			for(j=0;j<N;j++)
			scf("%lld",&b[i][j]);
		}
		if(!is_pre()){
			puts("NO");
			continue;
		}
		if(is_ok())
		puts("YES");
		else
		puts("NO");
	}
	return 0;
}
相关标签: 2-Sat OJ题