敘述性說明：

這給出了一個矩陣，原來的請求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_JUDGEfreopen("G:/in.txt","r",stdin);//freopen("G:/out.txt","w",stdout);#endifint 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");} }

版權聲明：本文博客原創文章。博客，未經同意，不得轉載。

轉載于:https://www.cnblogs.com/gcczhongduan/p/4676513.html

總結

以上是生活随笔為你收集整理的HDU4421 Bit Magic 【2-sat】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。