传送门:【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 ; }