{"id":68,"date":"2011-03-25T07:46:39","date_gmt":"2011-03-24T23:46:39","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=68"},"modified":"2012-03-03T07:47:44","modified_gmt":"2012-03-02T23:47:44","slug":"poj-3678-katu-puzzle","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-3678-katu-puzzle\/","title":{"rendered":"POJ 3678. Katu Puzzle"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u7ed9\u5b9a n \u4e2a\u5e03\u5c14\u53d8\u91cf\uff0c\u6ee1\u8db3 m \u7ec4\u903b\u8f91\u7b49\u5f0f\u3002<br \/>\n\u95ee\u662f\u5426\u5b58\u5728\u4e00\u79cd\u8d4b\u503c\u65b9\u6848\uff0c\u4f7f\u5f97\u6240\u6709\u7684\u7b49\u5f0f\u6210\u7acb\u3002<br \/>\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>&#8230; \u7565\u3002\u3002\u3002\u53cd\u6b63\u5c31\u662f\u5212\u5230 2-SAT \u5c31\u53ef\u4ee5\u505a\u4e86\u561b\u3002\u3002<br \/>\n\u4e0b\u9762\u4e3e\u4e24\u4e2a\u4f8b\u5b50\u3002\u3002<\/p>\n<p>\u6bd4\u5982\u8bf4 A or B == 1 \u8fd9\u6837\u7684\u5f0f\u5b50\u3002\u3002\u3002<br \/>\n\u5982\u679c A \u8d4b\u503c\u4e3a 0 \u7684\u8bdd\u90a3\u4e48 B \u5fc5\u987b\u662f 1\uff0c\u56e0\u6b64\u8fde\u8fb9 A0 -> B1\u3002\u3002\u3002<br \/>\n\u3002\u3002\u3002\u3002\u3002\u3002<\/p>\n<p>\u7136\u540e\u5982\u679c\u662f A and B == 1 \u7684\u8bdd\u3002\u3002\u3002<br \/>\n\u6b64\u65f6\u5982\u679c A \u8d4b\u503c\u4e3a 0 \uff1f\u3002\u3002\u4e0d \u3002\u3002A \u4e0d\u53ef\u4ee5\u8d4b\u503c\u4e3a 0 \u3002\u3002\u3002<br \/>\n\u4e0d\u5fc5\u62d8\u6ce5\u4e8e\u4e4b\u524d\u7684\u9650\u5236\u3002\u3002\u3002\u6211\u4eec\u8fde\u4e00\u6761 A0 -> A1 \u7684\u8fb9\u5c31\u53ef\u4ee5\u4e86\uff01<\/p>\n<pre lang=\"cpp\" file=\"2-SAT.cpp\">\r\n#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nconst int INF = 0x7fffffff;\r\nconst int N = 2000;\r\nvector<int> adj[N];\r\nint d[N], l[N], f[N];\r\nint st[N], top, cnt;\r\nint n, m;\r\n\r\nvoid dfs(int u){\r\n\td[u] = l[u] = ++cnt;\r\n\tst[top++] = u;\r\n\tfor (int i=0;i<adj[u].size();i++){\r\n\t\tint v = adj[u][i];\r\n\t\tif (d[v] < d[u]){\r\n\t\t\tif (d[v] == 0) dfs(v);\r\n\t\t\tl[u] = min(l[u], l[v]);\r\n\t\t}\r\n\t}\r\n\t\r\n\tif (l[u]==d[u]){\r\n\t\tdo{\r\n\t\t\tf[st[--top]] = u;\r\n\t\t\td[st[top]] = INF;\r\n\t\t}while (st[top]!=u);\r\n\t}\r\n}\r\n\r\nvoid init(){\t\r\n\tmemset(adj, 0, sizeof(adj));\r\n\t\r\n\tint a, b, c; char op, bk;\r\n\tfor (int i = 0; i < m; i ++){\r\n\t\tscanf(\"%d%d%d %c%c%c\", &#038;a, &#038;b, &#038;c, &#038;op, &#038;bk, &#038;bk);\r\n\t\tswitch (op) {\r\n\t\t\tcase 'A':\r\n\t\t\t\tif (c==0)\r\n\t\t\t\t\tadj[2*a+1].push_back(2*b), adj[2*b+1].push_back(2*a);\r\n\t\t\t\telse {\r\n\t\t\t\t\tadj[2*a].push_back(2*a+1), adj[2*b].push_back(2*b+1);\r\n\t\t\t\t\tadj[2*a+1].push_back(2*b+1), adj[2*b+1].push_back(2*a+1);\r\n\t\t\t\t}\r\n\t\t\t\tbreak;\r\n\t\t\tcase 'O':\r\n\t\t\t\tif (c==1)\r\n\t\t\t\t\tadj[2*a].push_back(2*b+1), adj[2*b].push_back(2*a+1);\r\n\t\t\t\telse {\r\n\t\t\t\t\tadj[2*a+1].push_back(2*a), adj[2*b+1].push_back(2*b);\r\n\t\t\t\t\tadj[2*a].push_back(2*b), adj[2*b].push_back(2*a);\r\n\t\t\t\t}\r\n\t\t\t\tbreak;\r\n\t\t\tdefault: \/\/'X'\r\n\t\t\t\tif (c==0){\r\n\t\t\t\t\tadj[2*a].push_back(2*b), adj[2*b].push_back(2*a);\r\n\t\t\t\t\tadj[2*a+1].push_back(2*b+1), adj[2*b+1].push_back(2*a+1);\r\n\t\t\t\t}\r\n\t\t\t\telse {\r\n\t\t\t\t\tadj[2*a].push_back(2*b+1), adj[2*b+1].push_back(2*a);\r\n\t\t\t\t\tadj[2*a+1].push_back(2*b), adj[2*b].push_back(2*a+1);\r\n\t\t\t\t}\r\n\t\t\t\tbreak; \/\/Orz..a\r\n\t\t}\r\n\t}\r\n}\r\n\r\nvoid solve(){\r\n\tmemset(d, 0, sizeof(d));\r\n\tcnt = top = 0;\r\n\tfor (int i=0;i<2*n;i++)\r\n\t\tif (!d[i]) dfs(i);\r\n\t\r\n}\r\n\r\nbool check(){\r\n\tfor (int i=0;i<n;i++)\r\n\t\tif (f[2*i] == f[2*i+1]) return false;\r\n\treturn true;\r\n}\r\n\r\nint main(){\r\n\t\/\/freopen(\"in.txt\", \"r\", stdin);\r\n\twhile (scanf(\"%d%d\", &#038;n, &#038;m) != EOF){\r\n\t\tinit(); solve();\r\n\t\tcout << (check() ? \"YES\" : \"NO\") << endl;\r\n\t}\r\n}\r\n<\/pre>\n<p><bk><bk><bk><bk><br \/>\n<bk><bk><bk><bk><\/p>\n<h3>External link :<\/h3>\n<p><a href=\"http:\/\/poj.org\/problem?id=3678\">http:\/\/poj.org\/problem?id=3678<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u7ed9\u5b9a n \u4e2a\u5e03\u5c14\u53d8\u91cf\uff0c\u6ee1\u8db3 m \u7ec4\u903b\u8f91\u7b49\u5f0f\u3002 \u95ee\u662f\u5426\u5b58\u5728\u4e00\u79cd\u8d4b\u503c\u65b9\u6848\uff0c\u4f7f\u5f97\u6240\u6709\u7684\u7b49\u5f0f\u6210\u7acb\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[19],"tags":[44],"class_list":["post-68","post","type-post","status-publish","format-standard","hentry","category-poj","tag-2-sat"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-16","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/68","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=68"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/68\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=68"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=68"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=68"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}