2-SAT入門題，強聯通分量縮點之后，如果夫妻位于同一強聯通分量，則無解。

#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<algorithm> using namespace std;const int maxn=2005; int N,M; int A1,A2,C1,C2; vector<int>G[maxn]; vector<int>FG[maxn];int Belong[maxn],flag[maxn]; stack<int>S; int Block;void init() {if(!S.empty()) S.pop();for(int i=0; i<2*N; i++) G[i].clear();for(int i=0; i<2*N; i++) FG[i].clear();memset(Belong,0,sizeof Belong);memset(flag,0,sizeof flag);Block=0; }void Add(int A1,int A2,int C1,int C2) {int ID1=2*A1+C1;int ID2=2*A2+C2;G[ID1].push_back(ID2^1);G[ID2].push_back(ID1^1);FG[ID2^1].push_back(ID1);FG[ID1^1].push_back(ID2); }void dfs1(int now) {flag[now]=1;for(int i=0; i<G[now].size(); i++)if(!flag[G[now][i]])dfs1(G[now][i]);S.push(now); }void dfs2(int now) {Belong[now]=Block;for(int i=0; i<FG[now].size(); i++)if(!Belong[FG[now][i]])dfs2(FG[now][i]); }int main() {while(~scanf("%d%d",&N,&M)){init();for(int i=0; i<M; i++){scanf("%d%d%d%d",&A1,&A2,&C1,&C2);Add(A1,A2,C1,C2);}for(int i=0; i<2*N; i++) if(!flag[i]) dfs1(i);while(!S.empty()){int Top=S.top();S.pop();if(!Belong[Top]){Block++;dfs2(Top);}}int ans=1;for(int i=0; i<N; i++){if(Belong[2*i]==Belong[2*i+1]){ans=0;break;}}if(ans==1) printf("YES\n");else printf("NO\n");}return 0; }

?

轉載于:https://www.cnblogs.com/zufezzt/p/4904065.html

總結

以上是生活随笔為你收集整理的HDU 3062 Party的全部內容，希望文章能夠幫你解決所遇到的問題。

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