织梦网站上传的文章只显示摘要不显示内容如何修改,seo综合排名优化,找人做网站要拿到源代码吗,sem什么意思中文题 题意略 学2-sat啦啦啦 2-sat就是 矛盾的 ($x、x’$不能同时取) m对人 相互也有限制条件 取出其中n个人 也有可能是把一件东西分成 取/不取 相矛盾的两种情况 (那就要拆点啦~) 取其中n件 做法是 暴力 和 强连通 两种 重点在于建图#xff1a; 对于x#xff0c;记 取…中文题 题意略 学2-sat啦啦啦 2-sat就是 矛盾的 ($x、x’$不能同时取) m对人 相互也有限制条件 取出其中n个人 也有可能是把一件东西分成 取/不取 相矛盾的两种情况 (那就要拆点啦~) 取其中n件 做法是 暴力 和 强连通 两种 重点在于建图 对于x记 取 为 $x$ 不取 为$x’$ 对于y记 取 为 $y$ 不取 为$y’$ 对于 一对矛盾u($u、u$) 和 一对矛盾v($v、v$) 建立$u\Rightarrow v$的含义是 取$u$ 则 必须取$v$ 那么对于事件“x、y不能同时选” 需要建立两条边 $x\Rightarrow y$(取$x$ 则必定 取$y’$也就是不取$y$) 、 $y\Rightarrow x$(取$y$ 则必定 取$x’$也就是不取$x$) “x、y不能同时不选” $x\Rightarrow y$(取$x’$也就是不取$x$ 则必须取$y$) 、 $y’\Rightarrow x$(取$y’$也就是不取$y$ 则必须取$x$) “x、y要同时选” $x\Rightarrow y$(取$x$ 则 必须取$y$) “x、y要同时不选” $x’\Rightarrow y’$(取$x’$ 则 必须取$y’$) 还有个比较特殊的 “x必须选” 这个建边的方法(类似于反证法)是 建立不能取x的边 $x\Rightarrow x$ 结合边的含义来看上述边的意义是取x’(不取x) 则必须取x 显然这是矛盾的 那么对于取x’ 这个方案是不行的也就是必须取x 呃(--;)这个有点绕。。。 就是 不取x是不行的 那就是取x咯 在算法运行的过程中 一旦出现矛盾 比如上述的取x(不取x) 又要取x的情况 那么就可以开始回溯了 这个方案是行不通的 噢 回到这道题 这道题 丈夫和妻子不能同时出席 就是x和x’ 了 比如案例0号丈夫和1号丈夫不能同时选 那就建 0丈夫$\Rightarrow$ 1妻子 、 1丈夫$\Rightarrow$ 0妻子 的两条边即可 然后套个九爷的模板啦啦啦就好啦 1 #include bits/stdc.h2 using namespace std;3 typedef long long LL;4 typedef pairint, int PI;5 #define INF 0x3f3f3f3f6 7 const int N1005*2;8 const int MN*N;9 //注意n是拆点后的大小 即 n 1 N为点数(注意要翻倍) M为边数 i10为i真 i11为i假
10 struct Edge
11 {
12 int to, nex;
13 }edge[M];
14 //注意 N M 要修改
15 int head[N], edgenum;
16 void addedge(int u, int v)
17 {
18 Edge E{v, head[u]};
19 edge[edgenum]E;
20 head[u]edgenum;
21 }
22
23 bool mark[N];
24 int Stack[N], top;
25 void init()
26 {
27 memset(head, -1, sizeof(head));
28 edgenum0;
29 memset(mark, 0, sizeof(mark));
30 }
31
32 bool dfs(int x)
33 {
34 if(mark[x^1])
35 return false;//一定是拆点的点先判断
36 if(mark[x])
37 return true;
38 mark[x]true;
39 Stack[top]x;
40 for(int ihead[x];i!-1;iedge[i].nex)
41 if(!dfs(edge[i].to))
42 return false;
43
44 return true;
45 }
46
47 bool solve(int n)
48 {
49 for(int i0;in;i2)
50 if(!mark[i] !mark[i^1])
51 {
52 top0;
53 if(!dfs(i))
54 {
55 while(top)
56 mark[Stack[--top]]false;
57 if(!dfs(i^1))
58 return false;
59 }
60 }
61 return true;
62 }
63
64 int main()
65 {
66 int n;
67 while(~scanf(%d, n))
68 {
69 int m;
70 scanf(%d, m);
71 init();
72 while(m--)
73 {
74 int a1, a2, c1, c2;
75 scanf(%d%d%d%d, a1, a2, c1, c2);
76 addedge(2*a1c1, 2*a2-c21);
77 addedge(2*a2c2, 2*a1-c11);
78 }
79 solve(n)? puts(YES): puts(NO);
80 }
81 return 0;
82 } HDOJ 3062 转载于:https://www.cnblogs.com/Empress/p/4737520.html
