首页 > 代码库 > hdu1824-Let's go home:图论2-SAT
hdu1824-Let's go home:图论2-SAT
关键在于找出一定矛盾的条件,设一队的3个人为(a,b,c),a为队长,那么(a不留下,b不留下)矛盾,(a不留下,c不留下)矛盾; 对于每一对队员,(a留下,b留下)矛盾。
把模型建好,剩下的就是套模板了。
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 3000+10; 7 8 struct TwoSAT 9 {10 int n;11 vector<int> G[maxn*2];12 bool mark[maxn*2];13 int S[maxn*2], c;14 15 bool dfs(int x)16 {17 if (mark[x^1]) return false;18 if (mark[x]) return true;19 mark[x] = true;20 S[c++] = x;21 for (int i = 0; i < G[x].size(); i++)22 if (!dfs(G[x][i])) return false;23 return true;24 }25 26 void init(int n)27 {28 this->n = n;29 for (int i = 0; i < n*2; i++) G[i].clear();30 memset(mark, 0, sizeof(mark));31 }32 33 // x = xval or y = yval34 void add_clause(int x, int xval, int y, int yval)35 {36 x = x * 2 + xval;37 y = y * 2 + yval;38 G[x^1].push_back(y);39 G[y^1].push_back(x);40 }41 42 bool solve()43 {44 for(int i = 0; i < n*2; i += 2)45 if(!mark[i] && !mark[i+1])46 {47 c = 0;48 if(!dfs(i))49 {50 while(c > 0) mark[S[--c]] = false;51 if(!dfs(i+1)) return false;52 }53 }54 return true;55 }56 };57 58 59 ///////////////////////////////////////////////////////////////60 #include <iostream>61 #include <cmath>62 using namespace std;63 TwoSAT solver;64 65 int main()66 {67 int t,m;68 while(~scanf("%d%d",&t,&m))69 {70 solver.init(t*3);71 for(int i=0;i<t;i++)72 {73 int a,b,c;74 scanf("%d%d%d",&a,&b,&c);75 solver.add_clause(a,0,b,0); // 0表示不留下,1表示留下76 solver.add_clause(a,0,c,0);77 //solver.add_clause(b,1,c,0);78 //solver.add_clause(c,1,b,0);79 }80 81 for(int i=0;i<m;i++)82 {83 int a,b;84 scanf("%d %d",&a,&b);85 solver.add_clause(a,1,b,1);86 }87 printf("%s\n",solver.solve()?"yes":"no");88 }89 return 0;90 }
hdu1824-Let's go home:图论2-SAT
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。