有n个变量，每一个变量都是bool类型的，除了这n个变量以外，还有m个关系表达式，关系表达式差不多是x1&x2=false。求能否给这n个变量找出一个赋值的方法，使得满足所有的表达式。
将每个变量x拆成false和true两个点。
假设x1&x2=false，则x1和x2必有一个=false，于是连边(x1的true，x2的false),连边(x2的true，x1的false)，即若x1=true，则必有x2=false；若x2=true，则必有x1=true。
注意不能连边(x2的false，x1的true)，因为当x2=false时，x1不一定=true，关系是不明确的，只有当关系明确时才可以连边。
跑tarjan强连通分量，同一个SCC中的点是选了一个就一定要选其他所有的，若一个点和它的反点都在同一个强连通分量中则无解。
构造解的方案，按照拓扑序从大到小选择，tarjan时求出的SCC的编号就是逆拓扑徐，构造时优先选择SCC编号小的那一方。
m个四元组i,a,j,b表示x[i]=a或x[j]=b,a,b=0或1.以0为原点，1为反点建图。
for(int i=1;i<=m;i++){
int a,b,x,y;
cin>>a>>x>>b>>y;
if(!x&&!y)add(a+n,b),add(b+n,a);/*a=0||b=0,a=1->b=0,b=1->a=0*/
if(!x&&y)add(a+n,b+n),add(b,a);/*a=0||b=1,a=1->b=1,b=0->a=0*/
if(x&&!y)add(a,b),add(b+n,a+n);/*a=1||b=0,a=0->b=0,b=1->a=1*/
if(x&&y)add(a,b+n),add(b,a+n);/*a=1||b=1,a=0->b=1,b=0->a=1*/
}
for(int i=1;i<=(n<<1);i++)if(!ipt[i])tarjan(i);
for(int i=1;i<=n;i++)if(bl[i]==bl[i+n])return puts("IMPOSSIBLE"),0;
puts("POSSIBLE");
for(int i=1;i<=n;i++)cout<<(bl[i]<bl[i+n]?0:1)<<' ';
每个评委喜欢编号x的菜的满式为mx，汉式为hx，给出每个评委喜欢的两种菜及其风格，选手对每个评委满足其一即可通过，问是否可以通过。将编号转化为数字后，设满式做法为原点x，汉式做法为反点x+n，对应关系连边即可。
for(int i=1;i<=m;i++){
string a,b;
cin>>a>>b;
int x=0,y=0,k=1;
while(a[k]>='0'&&a[k]<='9')x=(x<<1)+(x<<3)+a[k++]-'0';
k=1;
while(b[k]>='0'&&b[k]<='9')y=(y<<1)+(y<<3)+b[k++]-'0';
if(a[0]=='m'){
if(b[0]=='m')add(x+n,y),add(y+n,x);
else add(x+n,y+n),add(y,x);
}
else{
if(b[0]=='m')add(x,y),add(y+n,x+n);
else add(x,y+n),add(y,x+n);
}
}
n个党派集会，每个党派两个代表，2i-1和2i属于一个党派，m对关系，a和b互相厌恶，求构造一处出席会议的方案。由于每个党派必须有人出席会议，若不选x，就必须选x的同伴，连边即可，注意判断反点不是x+n,而是x+1。
inline int id(int x){
return (x&1)?x+1:x-1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,id(b));
add(b,id(a));
}
n<<=1;
for(int i=1;i<=n;i++)if(!ipt[i])tarjan(i);
for(int i=1;i<=n;i+=2)if(bl[i]==bl[i+1])return cout<<"NIE",0;
for(int i=1;i<=n;i+=2)cout<<(bl[i]<bl[i+1]?i:id(i))<<'\n';
return 0;
}
给出m条边，和n个点的哈密顿回路，问该图是否是一个平面图。哈密顿回路形成一个环，对于不在环上的两条边，若相交，那么不可能同时在环内或环外，对应连边。
for(int i=1;i<=m;i++)cin>>from[i]>>to[i];
for(int i=1;i<=n;i++){
int x;cin>>x;
g[x]=i;
}
if(m>3*n-6){
cout<<"NO\n";
continue;
}
for(int i=1;i<m;i++)for(int j=i+1;j<=m;j++){
int a=g[from[i]],b=g[to[i]],c=g[from[j]],d=g[to[j]];
if(a>b)swap(a,b);
if(c>d)swap(c,d);
if(check(a,b,c,d))add(i,j+m),add(j+m,i),add(i+m,j),add(j,i+m);
}
划分成k个部分的无向图，选择一些关键点，使得每个部分恰好有一个，每条边至少有一端是关键点。注意每条边是至少有一个不是恰好有一个，对于每条边的两个端点，不选一个则必须选另外一个，对于一个部分中的点，选了它就不能选其他点，但是这样连边达到了N^2级别，需要前后缀和优化建图。对于一个点x，前缀prex，后缀点prex'，连边方式x->prex,prex'->x',前缀之间从小到大连边，后缀之间从大到小连边。
#define p(x) (x)//选x
#define p0(x) (x+n)//不选x
#define p1(x) (x+n+n)//前缀
#define p2(x) (x+n+n+n)//后缀
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
add(p0(x),p(y));
add(p0(y),p(x));
}
for(int i=1;i<=k;i++){
int w;
cin>>w;
for(int j=1;j<=w;j++){
cin>>a[j];
add(p(a[j]),p1(a[j]));//构建前缀
add(p2(a[j]),p0(a[j]));//构建后缀
}
for(int j=2;j<=w;j++){
add(p1(a[j-1]),p1(a[j]));//从小到大前缀累加
add(p2(a[j]),p2(a[j-1]));//从大到小后缀累加
add(p(a[j]),p2(a[j-1]));
add(p1(a[j-1]),p0(a[j]));
}
}
n场游戏，每场游戏有一张地图，没场地图选择一辆车，A,B,C三种车，a,b,c,x四中地图，A不可用于a，B不可用于b，C不可用于c，x可以适应所有车，给出要进行游戏的地图，还有一些要求i,hi,j,hj表示若i场使用hi车，则j场必须使用hj车，构造一种方案。这里不再是普通的2-SAT的选与不选关系，假设对于地图a，不能选择A，那么设原点为B，反点为C，对于地图b，原点为A，反点为C，对于地图c，原点为A,反点为B，对于地图x，2^d枚举每张x是不用A还是不用B，这样就包含了ABC三种情况。对于连边，若i场无法用hi则跳过，若j场无法用hj，则说明i场必须用另一辆，否则，i场用hi连边j场用hj，j场不用hj连边i场不用hi。构造方案时，SCC编号小的为第一张地图，否则选第二张地图。
inline bool check(){
for(int i=1;i<=(n<<1);i++)if(!ipt[i])tarjan(i);
for(int i=1;i<=n;i++){
if(bl[i]==bl[i+n])return false;
switch(c[i]){
case 'A':ans[i]=(bl[i]<bl[i+n])?'B':'C';break;
case 'B':ans[i]=(bl[i]<bl[i+n])?'A':'C';break;
case 'C':ans[i]=(bl[i]<bl[i+n])?'A':'B';break;
}
}
for(int i=1;i<=n;i++)cout<<ans[i];
return true;
}
inline int getid(int x,char ch){
switch(c[x]){
case 'A':return x+=(ch!='B')*n;
case 'B':return x+=(ch!='A')*n;
case 'C':return x+=(ch!='A')*n;
}
}
inline int id(int x){
return x>n?x-n:x+n;
}
int main(){
cin>>n>>d>>c+1>>m;
for(int i=1;i<=m;i++)cin>>x[i]>>h1[i]>>y[i]>>h2[i];
for(int i=1;i<=n;i++)if((c[i]-=32)&&c[i]=='X')xmp[++k]=i;
for(int s=0;s<(1<<d);s++){
clear();
for(int i=1;i<=d;i++)c[xmp[i]]=(s&(1<<i-1))?'A':'B';
for(int i=1;i<=m;i++){
if(c[x[i]]==h1[i])continue;//第i场比赛不能用hi
int a=getid(x[i],h1[i]),b=getid(y[i],h2[i]);
if(c[y[i]]==h2[i]){//第j场比赛不能用hj
add(a,id(a));
continue;
}
add(a,b);
add(id(b),id(a));
}
if(check())exit(0);
}
cout<<-1;
return 0;
}
n个人分成后勤组和同谋组，要求后勤组必须都是熟人，同谋组必须都是陌生人，每一部分至少有一个人，求方案数。以原点为后勤组，反点为同谋组，当x与y是熟人时，若x在同谋组则y必须在后勤组，当x与y是陌生人时，若x在后勤组，则y必须在同谋组，于是得到了连边关系。tarjan求SCC后记录后勤组和同谋组都有哪些人，当x在后勤组且熟人y在同谋组时，y是x的冲突点，当x在同谋组且陌生人y在后勤组时，y时x的冲突点。从已有解拓展，要么交换两个阵营，要么最多将一个人替换阵营，当一个点的冲突点数是0且自己阵营人数大于1时，可以直接放到对面阵营，这里统计一下两个阵营冲突点数为0的数的个数之后乘法原理。对于冲突点数为1的数x，若其冲突点y没有冲突点，则可以交换x和y，其他冲突点数大于1的点不可能交换到达对面。
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)mp[i][j]?add(i+n,j):add(i,j+n);
for(int i=1;i<=(n<<1);i++)if(!ipt[i])tarjan(i);
for(int i=1;i<=n;i++){
if(bl[i]==bl[i+n])return cout<<0,0;
if(bl[i]<bl[i+n])logi[++logi[0]]=i;
else cons[++cons[0]]=i,flag[i]=1;
}
for(int i=1;i<=logi[0];i++)for(int j=1;j<=cons[0];j++)if(mp[logi[i]][cons[j]])sum[logi[i]]++,match[logi[i]]=cons[j];
for(int i=1;i<=cons[0];i++)for(int j=1;j<=logi[0];j++)if(!mp[cons[i]][logi[j]])sum[cons[i]]++,match[cons[i]]=logi[j];
ans=(logi[0]&&cons[0]);
int a=0,b=0;
for(int i=1;i<=n;i++){
if(sum[i]==1&&!sum[match[i]])ans++;
else if(!sum[i]){
if((flag[i]&&cons[0]>1)||(!flag[i]&&logi[0]>1))ans++;
flag[i]?a++:b++;
}
}
cout<<ans+a*b;