现在的位置: 首页 > 综合 > 正文

【POJ】3207 Ikki’s Story IV – Panda’s Trick 2-sat

2017年10月15日 ⁄ 综合 ⁄ 共 1620字 ⁄ 字号 评论关闭

传送门:【POJ】3207 Ikki's Story IV - Panda's Trick

题目分析:2-sat问题。

存下每一条线段,如果两条线段出现交集则这两条线段不能在同一侧,用A,A'表示一条线段的不同侧,如果线段A,B不能在同一侧则建边<A,B'>,<B,A'>,同时还须建边<A',B>,<B',A>,因为A,B不能同时在一侧也不能同时在另一侧。

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 2005 ;
const int MAXE = 2333333 ;

struct Edge {
	int v ;
	Edge* next ;
} ;

struct Line {
	int l , r ;
	void input () {
		scanf ( "%d%d" , &l , &r ) ;
		if ( l > r ) swap ( l , r ) ;
	}
} ;

Edge E[MAXE] , *H[MAXN] , *cur ;
int dfn[MAXN] , low[MAXN] , scc[MAXN] ;
int S[MAXN] , top ;
int dfs_clock , scc_cnt ;
int n , m ;
Line l[MAXN] ;

void init () {
	top = dfs_clock = scc_cnt = 0 ;
	cur = E ;
	CLR ( H , 0 ) ;
	CLR ( scc , 0 ) ;
	CLR ( dfn , 0 ) ;
}

void addedge ( int u , int v ) {
	cur -> v = v ;
	cur -> next = H[u] ;
	H[u] = cur ++ ;
}

void tarjan ( int u ) {
	dfn[u] = low[u] = ++ dfs_clock ;
	S[top ++] = u ;
	for ( Edge* e = H[u] ; e ; e = e -> next ) {
		int v = e -> v ;
		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] ) {
		++ scc_cnt ;
		while ( 1 ) {
			int v = S[-- top] ;
			scc[v] = scc_cnt ;
			if ( v == u ) break ;
		}
	}
}

/*
void scanf ( int& x , char c = 0 ) {
	while ( ( c = getchar () ) < '0' || c > '9' ) ;
	x = c - '0' ;
	while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}
*/

int solve () {
	init () ;
	REP ( i , 0 , m ) l[i].input () ;
	REP ( i , 0 , m ) REP ( j , i + 1 , m ) {
		if ( l[i].l < l[j].l && l[j].l < l[i].r && l[i].r < l[j].r ||
		     l[j].l < l[i].l && l[i].l < l[j].r && l[j].r < l[i].r ) {
			addedge ( i << 1 , j << 1 | 1 ) ;
			addedge ( j << 1 , i << 1 | 1 ) ;
			addedge ( i << 1 | 1 , j << 1 ) ;
			addedge ( j << 1 | 1 , i << 1 ) ;
		}
	}
	REP ( i , 0 , m << 1 ) if ( !dfn[i] ) tarjan ( i ) ;
	REP ( i , 0 , m ) if ( scc[i << 1] == scc[i << 1 | 1] ) return 0 ;
	return 1 ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) )
		printf ( solve () ? "panda is telling the truth...\n" : "the evil panda is lying again\n" ) ;
	return 0 ;
}

抱歉!评论已关闭.