[2-sat专练]poj 3683，hdu 1814，hdu 1824，hdu 3622，hdu 4115，hdu 4421

Priest John’s Busiest Day

题目
司仪必须在婚礼开始或结束时出现，考虑把第$i$i场婚礼拆成两个点
$i$i：表示司仪在婚礼$i$i开始时出现
$i+n$i+n：表示司仪在$i$i婚礼结束时出现

然后直接$O(n^2)$O(n2)建边????
①
如果$i,j$i,j的婚礼开始时间段有交叉
那么$i$i选开始，$j$j就只能选结束
②
如果$i$i开始时间段和$j$j结束时间段有交叉
那么$i$i选开始，$j$j就只能选开始
③
如果$i$i结束时间段和$j$j结束时间段有交叉
那么$i$i选结束，$j$j就只能选开始
④
如果$i$i结束和$j$j开始有交叉
那么$i$i选结束，$j$j就只能选结束

因为蒟蒻的双重循环写法问题，$i,j$i,j和$j,i$j,i都会遍历到，所以$i,j$i,j就只考虑单向连边，反边会在$j,i$j,i时判断

code

#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 2005
struct node {
	int Begin, End;
	node() {}
	node( int B, int E ) { Begin = B, End = E; }
}p[MAXN];
queue < int > q;
stack < int > st;
vector < int > G[MAXN], Edge[MAXN];
int n, cnt, tot;
int c[MAXN], du[MAXN], low[MAXN], dfn[MAXN], scc[MAXN], mbe[MAXN];
bool vis[MAXN];

void Tarjan( int u ) {
	dfn[u] = low[u] = ++ cnt;
	st.push( u );
	vis[u] = 1;
	for( int i = 0;i < G[u].size();i ++ ) {
		int v = G[u][i];
		if( ! dfn[v] )
			Tarjan( v ), low[u] = min( low[u], low[v] );
		else if( vis[v] )
			low[u] = min( low[u], dfn[v] );
	}
	if( low[u] == dfn[u] ) {
		int v; tot ++;
		do {
			v = st.top(); st.pop();
			scc[v] = tot;
			vis[v] = 0;
		} while( v != u );
	}
}

bool check( int i, int j ) {
	if( p[i].Begin >= p[j].End || p[i].End <= p[j].Begin )
		return 0;
	else
		return 1;
}

int main() {
	scanf( "%d", &n );
	for( int i = 1;i <= n;i ++ ) {
		int a, b, c, d, len;
		scanf( "%d:%d %d:%d %d", &a, &b, &c, &d, &len );
		p[i] = node( a * 60 + b, a * 60 + b + len );
		p[i + n] = node( c * 60 + d - len, c * 60 + d );
	}
	for( int i = 1;i <= n;i ++ )
		for( int j = 1;j <= n;j ++ ) {
			if( i == j ) continue;
			if( check( i, j ) ) G[i].push_back( j + n );
			if( check( i, j + n ) ) G[i].push_back( j );
			if( check( i + n, j ) ) G[i + n].push_back( j + n );
			if( check( i + n, j + n ) ) G[i + n].push_back( j );
		}
	for( int i = 1;i <= ( n << 1 );i ++ )
		if( ! dfn[i] ) Tarjan( i );
	for( int i = 1;i <= n;i ++ )
		if( scc[i] == scc[i + n] ) return ! printf( "NO\n" );
		else mbe[scc[i]] = scc[i + n], mbe[scc[i + n]] = scc[i];
	printf( "YES\n" );
	memset( c, -1, sizeof( c ) );
	for( int i = 1;i <= ( n << 1 );i ++ )
		for( int j = 0;j < G[i].size();j ++ )
			if( scc[i] == scc[G[i][j]] ) continue;
			else Edge[scc[G[i][j]]].push_back( scc[i] ), du[scc[i]] ++;
	for( int i = 1;i <= tot;i ++ )
		if( ! du[i] ) q.push( i );
	while( ! q.empty() ) {
		int u = q.front(); q.pop();
		if( c[u] == -1 ) c[u] = 1, c[mbe[u]] = 0;
		for( int i = 0;i < Edge[u].size();i ++ ) {
			int v = Edge[u][i];
			du[v] --;
			if( ! du[v] ) q.push( v );
		}
	}
	for( int i = 1;i <= n;i ++ )
		if( c[scc[i]] )
			printf( "%.2d:%.2d %.2d:%.2d\n", p[i].Begin / 60, p[i].Begin % 60, p[i].End / 60, p[i].End % 60 );
		else
			printf( "%.2d:%.2d %.2d:%.2d\n", p[i + n].Begin / 60, p[i + n].Begin % 60, p[i + n].End / 60, p[i + n].End % 60 );
	return 0;
}

Peaceful Commission

题目
$2i,2i-1$2i,2i−1要分开，那么直接彼此建边即可
要求字典序最小，其实发现我们是按顺序$dfs$dfs找解的，是能保证正确性的

code

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 16005
vector < int > G[MAXN];
int n, m, Top;
int st[MAXN];
bool flag[MAXN];

bool dfs( int u ) {
	if( flag[u ^ 1] ) return 0;
	if( flag[u] ) return 1;
	flag[u] = 1;
	st[++ Top] = u;
	for( int i = 0;i < G[u].size();i ++ )
		if( ! dfs( G[u][i] ) ) return 0;
	return 1;
}

bool two_sat() {
	for( int i = 0;i < ( n << 1 );i += 2 )
		if( ! flag[i] && ! flag[i ^ 1] ) {
			Top = 0;
			if( ! dfs( i ) ) {
				while( Top ) flag[st[Top]] = 0, Top --;
				if( ! dfs( i ^ 1 ) ) return 0;
			}
		}
	return 1;
}

int main() {
	while( ~ scanf( "%d %d", &n, &m ) ) {
		memset( flag, 0, sizeof( flag ) );
		for( int i = 0;i < ( n << 1 );i ++ )
			G[i].clear();
		for( int i = 1, a, b;i <= m;i ++ ) {
			scanf( "%d %d", &a, &b );
			a --, b --;
			G[a].push_back( b ^ 1 );
			G[b].push_back( a ^ 1 );
		}
		if( two_sat() ) {
			for( int i = 0;i < ( n << 1 );i += 2 )
				if( flag[i] ) printf( "%d\n", i + 1 );
				else printf( "%d\n", ( i ^ 1 ) + 1 );
		}
		else
			printf( "NIE\n" );
	}
	return 0;
}

Let’s go home

题目
注意区分‘对’，‘队’的意思哦~
$i$i：表示$i$i选手留下
$i+n$i+n：表示$i$i离开
①队长$i$i和两名队员$j,k$j,k
Ⅰ：如果队长离开，那么两位队员必须全部留下
建边$i+n,j$i+n,j和$i+n,k$i+n,k
Ⅱ：如果有一名队员离开，那么队长必须留下
注意同队的两名队员之间是不会相互影响的，换言之，一名队长和一名队员留下也是符合条件的
因此不能胡乱建边$(j,k),(j+n,k+n)$(j,k),(j+n,k+n)
建边$j+n,i$j+n,i和$k+n,i$k+n,i

②一对队员
注意两名队员同时离开也是符合题意的，所以不能胡乱建边$(i+n,j),(j+n,i)$(i+n,j),(j+n,i)
Ⅰ：如果$i$i留下，$j$j必须离开，建边$i,j+n$i,j+n
Ⅱ：如果$j$j留下，$i$i必须离开，建边$j,i+n$j,i+n

code

#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 30000
stack < int > st;
vector < int > G[MAXN];
int n, T, M, cnt, tot;
int dfn[MAXN], low[MAXN], scc[MAXN];

void tarjan( int u ) {
	dfn[u] = low[u] = ++ cnt;
	st.push( u );
	for( int i = 0;i < G[u].size();i ++ ) {
		int v = G[u][i];
		if( ! dfn[v] )
			tarjan( v ), low[u] = min( low[u], low[v] );
		else if( ! scc[v] )
			low[u] = min( low[u], dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int v; ++ tot;
		do {
			v = st.top(); st.pop();
			scc[v] = tot;
		} while( u != v );
	}
}

int main() {
	while( ~ scanf( "%d %d", &T, &M ) ) {
		n = T * 3;
		cnt = tot = 0;
		memset( dfn, 0, sizeof( dfn ) );
		memset( low, 0, sizeof( low ) );
		memset( scc, 0, sizeof( scc ) );
		for( int i = 1;i <= ( n << 1 );i ++ )
			G[i].clear();
		while( ! st.empty() ) st.pop();
		for( int i = 1, a, b, c;i <= T;i ++ ) {
			scanf( "%d %d %d", &a, &b, &c );
			G[a + n].push_back( b );
			G[a + n].push_back( c );
			G[b + n].push_back( a );
			G[c + n].push_back( a );
		}
		for( int i = 1, a, b;i <= M;i ++ ) {
			scanf( "%d %d", &a, &b );
			G[a].push_back( b + n );
			G[b].push_back( a + n );
		}
		for( int i = 0;i < ( n << 1 );i ++ )
			if( ! dfn[i] ) tarjan( i );
		bool flag = 0;
		for( int i = 0;i < n;i ++ )
			if( scc[i] == scc[i + n] ) { flag = 1; break; }
		if( flag ) printf( "no\n" );
		else printf( "yes\n" );
	}
	return 0;
}

Bomb Game

题目
二分＋2-sat
先把圆能移动的两个边界拆分成两个点，$i$i，$i+n$i+n
与上一题做法类似

考虑二分半径，要求不同圆之间不会有交集
也就是半径不会涉及，即两个之间距离要超过$r*2$r∗2

在每次二分的半径$mid$mid中判断是否有交叉
与上一道题建边思想类似，不再赘述

其实就是如果$a,b$a,b矛盾，那就建边$(a,b+n),(b,a+n)$(a,b+n),(b,a+n)
把矛盾的两个部分错开

code

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-5
#define MAXN 300
struct node {
	int x, y;
}p[MAXN];
vector < int > G[MAXN];
int cnt, tot, n, Top;
int dfn[MAXN], low[MAXN], scc[MAXN], st[MAXN];

void tarjan( int u ) {
	dfn[u] = low[u] = ++ cnt;
	st[++ Top] = u;
	for( int i = 0;i < G[u].size();i ++ ) {
		int v = G[u][i];
		if( ! dfn[v] )
			tarjan( v ), low[u] = min( low[u], low[v] );
		else if( ! scc[v] )
			low[u] = min( low[u], dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int v; ++ tot;
		do {
			v = st[Top --];
			scc[v] = tot;
		} while( u != v && Top );
	}
}

bool check() {
	for( int i = 1;i <= n;i ++ )
		if( scc[i] == scc[i + n] ) return 0;
	return 1;
}

double dis( int x1, int y1, int x2, int y2 ) {
	return sqrt( 1.0 * ( x1 - x2 ) * ( x1 - x2 ) + 1.0 * ( y1 - y2 ) * ( y1 - y2 ) );
}

int main() {
	while( ~ scanf( "%d", &n ) ) {
		for( int i = 1;i <= n;i ++ )
			scanf( "%d %d %d %d", &p[i].x, &p[i].y, &p[i + n].x, &p[i + n].y );
		double l = 0, r = 10000, mid;
		while( r - l > eps ) {
			cnt = tot = Top = 0;
			mid = ( l + r ) / 2;
			for( int i = 1;i <= ( n << 1 );i ++ )
				G[i].clear();
			memset( dfn, 0, sizeof( dfn ) );
			memset( low, 0, sizeof( low ) );
			memset( scc, 0, sizeof( scc ) );
			for( int i = 1;i < n;i ++ )
				for( int j = i + 1;j <= n;j ++ ) {
					if( dis( p[i].x, p[i].y, p[j].x, p[j].y ) < mid * 2 ) {
						G[i].push_back( j + n );
						G[j].push_back( i + n );
					}
					if( dis( p[i].x, p[i].y, p[j + n].x, p[j + n].y ) < mid * 2 ) {
						G[i].push_back( j );
						G[j + n].push_back( i + n );
					}
					if( dis( p[i + n].x, p[i + n].y, p[j].x, p[j].y ) < mid * 2 ) {
						G[i + n].push_back( j + n );
						G[j].push_back( i );
					}
					if( dis( p[i + n].x, p[i + n].y, p[j + n].x, p[j + n].y ) < mid * 2 ) {
						G[i + n].push_back( j );
						G[j + n].push_back( i );
					}
				}
			for( int i = 1;i <= n;i ++ )
				if( ! dfn[i] ) tarjan( i );
			if( check() ) l = mid;
			else r = mid;
		}
		printf( "%.2lf\n", mid );
	}
	return 0;
}

Eliminate the Conflict

题目
如果没有$bob$bob的出拳方式，单单只给$i,j$i,j轮的限制，这道题就会更加水
其实就算加上$bob$bob的限制也很简单…
对于$bob$bob的出拳，$Alice$Alice要想不输就必须打平或者赢
提前处理出$A$A在$i$i轮的两种出拳方式，然后根据后面给的限制，建边即可

code

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 20005
vector < int > G[MAXN];
int T, n, m, cnt, tot, Top;
int dfn[MAXN], low[MAXN], scc[MAXN], st[MAXN];
int bob[MAXN][2];

void tarjan( int u ) {
	dfn[u] = low[u] = ++ cnt;
	st[++ Top] = u;
	for( int i = 0;i < G[u].size();i ++ ) {
		int v = G[u][i];
		if( ! dfn[v] ) 
			tarjan( v ), low[u] = min( low[u], low[v] );
		else if( ! scc[v] )
			low[u] = min( low[u], dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int v; ++ tot;
		do {
			v = st[Top --];
			scc[v] = tot;
		} while( u != v && Top );
	}
}

int main() {
	scanf( "%d", &T );
	for( int Case = 1;Case <= T;Case ++ ) {
		memset( dfn, 0, sizeof( dfn ) );
		memset( low, 0, sizeof( low ) );
		memset( scc, 0, sizeof( scc ) );
		cnt = tot = Top = 0;
		for( int i = 1;i <= ( n << 1 );i ++ )
			G[i].clear();
		scanf( "%d %d", &n, &m );
		for( int i = 1;i <= n;i ++ ) {
			scanf( "%d", &bob[i][0] );
			bob[i][0] --;
			bob[i][1] = ( bob[i][0] + 1 ) % 3;
		}
		for( int i = 1, a, b, k;i <= m;i ++ ) {
			scanf( "%d %d %d", &a, &b, &k );
			if( ! k ) {
				if( bob[a][0] != bob[b][0] ) {
					G[a].push_back( b + n );
					G[b].push_back( a + n );
				}
				if( bob[a][0] != bob[b][1] ) {
					G[a].push_back( b );
					G[b + n].push_back( a + n );
				}
				if( bob[a][1] != bob[b][0] ) {
					G[a + n].push_back( b + n );
					G[b].push_back( a );
				}
				if( bob[a][1] != bob[b][1] ) {
					G[a + n].push_back( b );
					G[b + n].push_back( a );
				}
			}
			else {
				if( bob[a][0] == bob[b][0] ) {
					G[a].push_back( b + n );
					G[b].push_back( a + n );
				}
				if( bob[a][0] == bob[b][1] ) {
					G[a].push_back( b );
					G[b + n].push_back( a + n );
				}
				if( bob[a][1] == bob[b][0] ) {
					G[a + n].push_back( b + n );
					G[b].push_back( a );
				}
				if( bob[a][1] == bob[b][1] ) {
					G[a + n].push_back( b );
					G[b + n].push_back( a );
				}
			}
		}
		for( int i = 1;i <= ( n << 1 );i ++ )
			if( ! dfn[i] ) tarjan( i );
		bool flag = 1;
		for( int i = 1;i <= n;i ++ )
			if( scc[i] == scc[i + n] ) { flag = 0; break; }
		if( flag ) printf( "Case #%d: yes\n", Case );
		else printf( "Case #%d: no\n", Case );
	}
	return 0;
}

Bit Magic

题目
$i$i：表示$a[i]=1$a[i]=1
$i+n$i+n：表示$a[i]=0$a[i]=0

拆分成二进制，每一位来一次2-sat，有一位矛盾就$NO$NO

对于第$k$k位的数，$b[i][j]$b[i][j]二进制上第$k$k位有两种情况????
①$b[i][j]\&(1<<k)==1$b[i][j]&(1<<k)==1，$k$k位是$1$1

Ⅰ：$i\%2==1\&\&j\%2==1$i%2==1&&j%2==1
那么只要$i,j$i,j中有一个对应的$a$a值第$k$k位上为$1$1
也可以同时为1
所以如果$a[i]$a[i]第$k$k位不是$1$1，$a[j]$a[j]就必须$1$1
建边$(i+n,j),(j+n,i)$(i+n,j),(j+n,i)

Ⅱ：$i\%2==0\&\&j\%2==0$i%2==0&&j%2==0
$i,j$i,j必须同时为$1$1，建边$(i,j),(j,i)$(i,j),(j,i)

Ⅲ：剩下的情况，一奇一偶
这个时候要调用异或的法则了，必须一个为$1$1，另一个$0$0才能异或出来$1$1
建边$(i,j+n),(j,i+n),(i+n,j),(j+n,i)$(i,j+n),(j,i+n),(i+n,j),(j+n,i)

②$b[i][j]\&(1<<k)==0$b[i][j]&(1<<k)==0，$k$k位是$0$0

Ⅰ：$i\%2==1\&\&j\%2==1$i%2==1&&j%2==1
为了满足$k$k位或出来的结果为$0$0，必须$i,j$i,j都为$0$0
建边$(i+n, j+n),(j+n,i+n)$(i+n,j+n),(j+n,i+n)

Ⅱ：$i\%2==0\&\&j\%2==0$i%2==0&&j%2==0
$i,j$i,j只要有一个不为$1$1
也可以同时不为1，所以当$i$i为0的时候，是不确定$j$j的取值，没有矛盾地方，无法进行建边
建边$(i,j+n),(j,i+n)$(i,j+n),(j,i+n)

Ⅲ：剩下的情况，一奇一偶
要么同时为$1$1，同时$0$0
建边$(i,j),(j,i),(i+n,j+n),(j+n,i+n)$(i,j),(j,i),(i+n,j+n),(j+n,i+n)

code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 1005
vector < int > G[MAXN];
int n, Top, cnt, tot;
int dfn[MAXN], low[MAXN], scc[MAXN], st[MAXN];
int b[MAXN][MAXN];

void tarjan( int u ) {
	dfn[u] = low[u] = ++ cnt;
	st[++ Top] = u;
	for( int i = 0;i < G[u].size();i ++ ) {
		int v = G[u][i];
		if( ! dfn[v] )
			tarjan( v ), low[u] = min( low[u], low[v] );
		else if( ! scc[v] )
			low[u] = min( low[u], dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int v; tot ++;
		do {
			v = st[Top --];
			scc[v] = tot;
		} while( u != v && Top );
	}
}

void init() {
	cnt = tot = Top = 0;
	memset( scc, 0, sizeof( scc ) );
	memset( dfn, 0, sizeof( dfn ) );
	for( int i = 0;i < ( n << 1 );i ++ )
		G[i].clear();
}

int main() {
	while( ~ scanf( "%d", &n ) ) {
		for( int i = 0;i < n;i ++ )
			for( int j = 0;j < n;j ++ )
				scanf( "%d", &b[i][j] );
		bool flag = 0;
		for( int i = 0;i < n;i ++ ) {
			for( int j = 0;j < n;j ++ )
				if( i == j && b[i][j] ) { flag = 1; break; }
				else if( b[i][j] != b[j][i] ) { flag = 1; break; }
			if( flag ) break;
		}
		if( flag ) { printf( "NO\n" ); break; }
		for( int k = 0;k < 31;k ++ ) {
			init();
			for( int i = 0;i < n;i ++ )
				for( int j = i + 1;j < n;j ++ ) {
					int temp = ( b[i][j] & ( 1 << k ) );
					if( temp ) {
						if( ( i & 1 ) && ( j & 1 ) ) {
							G[i + n].push_back( j );
							G[j + n].push_back( i );
						}
						else if( i % 2 == 0 && j % 2 == 0 ) {
							G[i].push_back( j );
							G[j].push_back( i );
						}
						else {
							G[i].push_back( j + n );
							G[i + n].push_back( j );
							G[j].push_back( i + n );
							G[j + n].push_back( i );
						}
					}
					else {
						if( ( i & 1 ) && ( j & 1 ) ) {
							G[i + n].push_back( j + n );
							G[j + n].push_back( i + n );
						}
						else if( i % 2 == 0 && j % 2 == 0 ) {
							G[i].push_back( j + n );
							G[j].push_back( i + n );
						}
						else {
							G[i].push_back( j );
							G[j].push_back( i );
							G[i + n].push_back( j + n );
							G[j + n].push_back( i + n );
						}
					}
				}
			for( int i = 0;i < ( n << 1 );i ++ )
				if( ! dfn[i] ) tarjan( i );
			for( int i = 0;i < n;i ++ )
				if( scc[i] == scc[i + n] ) {
					flag = 1;
					break;
				}
			if( flag ) break;
		}
		if( flag ) printf( "NO\n" );
		else printf( "YES\n" );
	}
	return 0;
} 

感觉这几道模板都挺水的…怎么回事？？
2-sat就是会建边就会A，凡事建完后直接tarjan