首页 > 代码库 > HDU4421 Bit Magic 【2-sat】
HDU4421 Bit Magic 【2-sat】
描述:
给出这样的一个矩阵,求原来的a数组
2-sat题,对每个位跑一边,跑31个位即可
具体建边
注意N=1的情况特判,还有检查对称元素是否相同
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <vector> #include <math.h> #define pb push_back #include <algorithm> using namespace std; int V; const int MAX_V=1111; vector<int> G[MAX_V]; vector<int> rG[MAX_V]; vector<int> vs; bool used[MAX_V]; int cmp[MAX_V]; void add_edge(int from ,int to){ //cout<<from<<"->"<<to<<endl; G[from].pb(to); rG[to].pb(from); } void dfs(int v){ used[v]=true; //cout<<G[v].size()<<"---"<<endl; for(int i=0;i<G[v].size();i++) if(!used[G[v][i]]) dfs(G[v][i]); vs.pb(v); } void rdfs(int v,int k){ used[v]=true; cmp[v]=k; for(int i=0;i<rG[v].size();i++) if(!used[rG[v][i]]) rdfs(rG[v][i],k); } int scc(){ memset(used,0,sizeof(used)); memset(cmp,0,sizeof(cmp)); vs.clear(); for(int v=0;v<V;v++) if(!used[v]) dfs(v); memset(used,0,sizeof(used)); int k=0; for(int i=vs.size()-1;i>=0;i--) if(!used[vs[i]]) rdfs(vs[i],k++); for(int i=0;i<MAX_V;i++){G[i].clear();rG[i].clear();} return k; } int g[555][555]; int main(){ #ifndef ONLINE_JUDGE freopen("G:/in.txt","r",stdin); //freopen("G:/out.txt","w",stdout); #endif int N; while(scanf("%d",&N)!=EOF){ V=2*N; bool con=false; for(int i=0;i<N;i++) for(int j=0;j<N;j++) scanf("%d",&g[i][j]); if(N==1){//N=1特判 puts("YES"); continue; } for(int i=0;i<N && !con;i++) for(int j=0;j<N && !con;j++){ if(g[i][j]!=g[j][i]){//对角线对称 puts("NO"); con=true; } } if(con) continue; for(int now=0;now<=30;now++){ for(int i=0;i<N;i++) for(int j=i+1;j<N;j++){ int num=(g[i][j]>>now)&1; if((i&1)&&(j&1)){ if(num){ add_edge(i+N,j); add_edge(j+N,i); }else{ add_edge(i,i+N); add_edge(j,j+N); } }else if(!(i&1)&&!(j&1)){ if(num){ add_edge(i+N,i); add_edge(j+N,j); }else{ add_edge(i,j+N); add_edge(j,i+N); } }else{ if(num){ add_edge(i,j+N); add_edge(j+N,i); add_edge(i+N,j); add_edge(j,i+N); }else{ add_edge(i,j); add_edge(j,i); add_edge(i+N,j+N); add_edge(j+N,i+N); } } } for(int i=0;i<2*N;i++) for(int j=0;j<G[i].size();j++) //printf("%d->%d\n",i,G[i][j]); scc(); for(int i=0;i<N;i++)//2-sat无解条件 if(cmp[i]==cmp[N+i]){ puts("NO"); con=true; break; } if(con) break; } if(con) continue; puts("YES"); } }
HDU4421 Bit Magic 【2-sat】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。