这题敲了好久，第一道入门题，还是看了别人的才懂的…… 题意：有n个结点在圆上，然后有m条边把这些结点连起来，可以在圆内连，也可以在圆外连接。然后题目求的就是能否得出一个方案，就是连接的没有相交的…… 思路：这入门题可以一眼就可以看出是2SAT问题了。设一结点 i ，然后2*i 为在圆内连接，2*i+1为在圆外连接；然后设另一结点为 j，然后2*j 为在圆内连接，2*j+1为在圆外连接；根据2S

这题没有用到2SAT的算法，不过用到了思想。挺好的，入门吧。 因为现在就是判断某两个人是不是在同一集合里，而2SAT正好就是解法这种问题的最好解法算法，其思想就是2个为布尔值的量一个真则另一个必假，一个假另一个必真。 所以设当前人为 i，则 i *2这个结点为真，那么根据2SAT，则 2*i+1为假。所以如果输入的a与b，如果!(a*2+1)&&b=true 或者 a&&!(b*2+1)=tr

题目链接：uva 1391 - Astronauts #include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespace std;const int maxn = 100005;struct TwoSAT {int n;bool mark

2SAT是P问题，能在多项式时间内解决。这里对方法之一进行总结。 测试数据格式如下： 1000000 -383037 -585864 575603 -494722 -628477 805085 -502855 685868 923336 -606921 -653863 424389 333542 -656925 -809061 874253 即范围为1~1000000，“-”号表示取逆。比

http://cplusoj.com/d/senior/p/SS231019C 我们进行这样的转化 则0/1必选一个，2/3必选一个 那么就变成一个2sat问题 两三角形有交，则一个选，一个不能选 对角三角形一个选，一个不选。一个不选，一个选 三角形不合法，则选向不选连边，代表必须不选 // 5.3k#include<bits/stdc++.h>using namespace