1 /* 2 HDU - 1824 3 主要是题目描述比较坑爹，注意：队长回家两队员都必须在，只要有一个队员回家，队长都必须在。 4 同时贴上一段看到的让我警醒的话： 5 “这里我说一个细节问题，很多初学者容易忽视 6 那就是边的链接方向。 7 到底是谁指向谁，这个问题，很多初学者容易混淆（比如本人。。） 8 其实问题的关键是考虑，额。。就用这个题来说吧。 9 关键是考虑，一个矛盾关系对里面，到底是两个人是能同时出现，还是能同时不出现 10 这个题里面，队长和队员，是两者可以同时出现的。但是两者却不能同时离开 11 而后面给的关系里面，是指两个人可以同时走，但是却不能同时都在” 12 2—sat 理解拆对象拆分成两个点（T，F） 13 建立好点之间的连通关系 14 我没将队员看成一点，而是每个人作为一个对象 15 */#include <stdio.h> 16 #include <stdlib.h> 17 #include <string.h> 18 #include <math.h> 19 #include <ctype.h> 20 #include <string> 21 #include <iostream> 22 #include <sstream> 23 #include <vector> 24 #include <queue> 25 #include <stack> 26 #include <map> 27 #include <list> 28 #include <set> 29 #include <algorithm> 30 #define INF 0x3f3f3f3f 31 #define LL long long 32 #define eps 1e-7 33 #define maxn 3100 34 using namespace std;struct TwoSAT{ int n; 35 vector<int> G[maxn*2];//注意点集的大小 36 bool mark[maxn*2];//联系《2-sat算法解析》中的红蓝标色，夫妻不能被标同一种颜色；因为仇人间没有连边，所以在图本身，不可能将两人标同一个颜色 37 int S[maxn*2],c;//存储当前被标记的点，可用于标记的回退 38 bool dfs(int x) 39 { if (mark[x^1]) return false;//真假同时被标记，逻辑矛盾 40 if (mark[x]) return true;//x被标记，意味着下面的节点也被标记，思想是记忆化搜索 41 mark[x]=true; 42 S[c++]=x; for(int i=0;i<G[x].size();i++) if(!dfs(G[x][i])) return false;//同一个强联通分量应该表上同一种颜色 43 return true; 44 } 45 void init(int n) 46 { this->n=n; for(int i=0;i<n*2;i++) G[i].clear(); 47 memset(mark,0,sizeof(mark)); 48 } 49 void add_edge(int u,int v)//这个地方灵活多变一点 50 { 51 G[u].push_back(v);// cout<<u<<"->"<<v<<endl; 52 } void addT(int a,int b,int c) 53 { 54 add_edge(2*a+1,2*b); 55 add_edge(2*a+1,2*c); 56 add_edge(2*b+1,2*a);// add_edge(2*b,2*c); 57 add_edge(2*c+1,2*a);// add_edge(2*c+1,2*b+1); 58 } bool solve() 59 { for(int i=0;i<n*2;i+=2) 60 { if(!mark[i] && !mark[i^1])//真假都没被标记才需dfs，思考一下，原书上写的是[mark+1],这是由i的取值和步长决定的，这里更改，使逻辑含义统一 61 { 62 c=0;//记得清零 63 if(!dfs(i))//将i标记为true 64 { while(c>0) mark[S[--c]]=false; if (!dfs(i^1)) return false;//更改初始标号颜色。只要有一个对象不能“二选一”，则2-sat无解 65 } 66 } 67 } return true; 68 } 69 }sat;//每个人都有一个编号x 70 //2x表示留下，2x+1表示回家 71 int T,M;int nextint() 72 { int x; 73 scanf("%d",&x); return x; 74 }int main() 75 { while(cin>>T>>M) 76 { 77 sat.init(T*3+1); for(int i=0;i<T;i++) 78 { int a,b,c; 79 a=nextint();b=nextint();c=nextint();// cin>>a>>b>>c; 80 sat.addT(a,b,c); 81 } for(int i=0;i<M;i++) 82 { int x,y; 83 x=nextint();y=nextint();// cin>>x>>y; 84 sat.add_edge(2*x,2*y+1); 85 sat.add_edge(2*y,2*x+1); 86 } if (sat.solve()) cout<<"yes"<<endl;else cout<<"no"<<endl; 87 } return 0; 88 }