TwoSAT典例使用

[html]
// File Name: uva1146.cpp 
// Author: bo_jwolf 
// Created Time: Thursday, May 09, 2013 PM12:10:09 HKT 
 
#include<vector> 
#include<list> 
#include<map> 
#include<set> 
#include<deque> 
#include<stack> 
#include<queue> 
#include<bitset> 
#include<algorithm> 
#include<functional> 
#include<numeric> 
#include<utility> 
#include<sstream> 
#include<iostream> 
#include<iomanip> 
#include<cstdio> 
#include<cmath> 
#include<cstdlib> 
#include<cstring> 
#include<ctime> 
//TwoSAT solver ; 
using namespace std; 
const int maxn = 2005 ; 
//nt n , T[ maxn ][ 2 ] ; 
 
/*twosat*/ 
struct TwoSAT 
{ 
    int n ; 
    vector< int > G[ maxn * 2 ] ; 
    bool mark[ maxn * 2 ]; 
    int S[ maxn * 2 ] , c ; 
    bool dfs( int x ) 
    { 
        if( mark[ x ^ 1 ] ) 
            return false ; 
        if( mark[ x ] ) 
            return true ; 
        mark[ x ] = true ; 
        S[ c++ ] = x; 
        for( int i = 0 ; i < G[x].size() ; i++ ) 
            if( !dfs( G[ x ][ i ] ) ) 
                    return false ; 
            return true ; 
    } 
 
    void init( int n ) 
    { 
        this -> n = n ; 
        for( int i = 0 ; i < n * 2 ; i++ ) 
            G[ i ].clear() ; 
        memset( mark , 0 , sizeof( mark ) ); 
    } 
 
    void add_clause( int x , int xval , int y , int yval ) 
    { 
        x = x * 2 + xval ; 
        y = y * 2 + yval ; 
        G[ x ^ 1 ].push_back( y ) ; 
        G[ y ^ 1 ].push_back( x ) ; 
    } 
 
    bool solve() 
    { 
        for( int i = 0 ; i < n * 2 ; i += 2 ) 
            if( !mark[ i ] && !mark[ i + 1 ] ) 
            { 
                c = 0 ; 
                if( !dfs( i ) ) 
                { 
                    while( c > 0 ) 
                        mark[ S[ --c ] ] = false ; 
                    if( !dfs( i + 1 ) ) 
                        return false ; 
                } 
            } 
        return true ; 
    } 
}; 
TwoSAT solver ; 
int n , T[ maxn ][ 2 ] ; 
 
bool test( int diff ) 
{ 
    solver.init( n ) ; 
    for( int i  = 0 ; i < n ; i++ ) 
        for( int a = 0 ; a < 2 ; a++ ) 
            for( int j = i + 1 ; j < n ; j++ ) 
                for( int b = 0 ; b < 2 ; b++ ) 
                    if( abs( T[ i ][ a ] - T[ j ][ b ] ) < diff ) 
                        solver.add_clause( i , a ^ 1 , j , b ^ 1 ) ; 
    return solver.solve() ; 
} 
int main() 
{ 
    while( scanf( "%d" , & n ) == 1 && n ) 
    { 
        int L = 0 , R = 0 ; 
        for( int i = 0 ; i < n ; i++ ) 
            for( int a = 0 ; a < 2 ; a++ ) 
            { 
                scanf( "%d" , &T[ i ][ a ] ) ; 
                R = max( R , T[ i ][ a ] ); 
            } 
            while( L < R ) 
            { 
                int M =  L + ( R - L + 1 ) / 2 ; 
                if( test( M ) ) 
                    L = M ; 
                else 
                    R = M - 1 ; 
            } 
            printf( "%d\n" , L ) ; 
    } 
    return 0; 
} 

// File Name: uva1146.cpp
// Author: bo_jwolf
// Created Time: Thursday, May 09, 2013 PM12:10:09 HKT

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<queue>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
//TwoSAT solver ;
using namespace std;
const int maxn = 2005 ;
//nt n , T[ maxn ][ 2 ] ;

/*twosat*/
struct TwoSAT
{
 int n ;
 vector< int > G[ maxn * 2 ] ;
 bool mark[ maxn * 2 ];
 int S[ maxn * 2 ] , c ;
 bool dfs( int x )
 {
  if( mark[ x ^ 1 ] )
   return false ;
  if( mark[ x ] )
   return true ;
  mark[ x ] = true ;
  S[ c++ ] = x;
  for( int i = 0 ; i < G[x].size() ; i++ )
   if( !dfs( G[ x ][ i ] ) )
     return false ;
   return true ;
 }

 void init( int n )
 {
  this -> n = n ;
  for( int i = 0 ; i < n * 2 ; i++ )
   G[ i ].clear() ;
  memset( mark , 0 , sizeof( mark ) );
 }

 void add_clause( int x , int xval , int y , int yval )
 {
  x = x * 2 + xval ;
  y = y * 2 + yval ;
  G[ x ^ 1 ].push_back( y ) ;
  G[ y ^ 1 ].push_back( x ) ;
 }

 bool solve()
 {
  for( int i = 0 ; i < n * 2 ; i += 2 )
   if( !mark[ i ] && !mark[ i + 1 ] )
   {
    c = 0 ;
    if( !dfs( i ) )
    {
     while( c > 0 )
      mark[ S[ --c ] ] = false ;
     if( !dfs( i + 1 ) )
      return false ;
    }
   }
  return true ;
 }
};
TwoSAT solver ;
int n , T[ maxn ][ 2 ] ;

bool test( int diff )
{
 solver.init( n ) ;
 for( int i  = 0 ; i < n ; i++ )
  for( int a = 0 ; a < 2 ; a++ )
   for( int j = i + 1 ; j < n ; j++ )
    for( int b = 0 ; b < 2 ; b++ )
     if( abs( T[ i ][ a ] - T[ j ][ b ] ) < diff )
      solver.add_clause( i , a ^ 1 , j , b ^ 1 ) ;
 return solver.solve() ;
}
int main()
{
 while( scanf( "%d" , & n ) == 1 && n )
 {
  int L = 0 , R = 0 ;
  for( int i = 0 ; i < n ; i++ )
   for( int a = 0 ; a < 2 ; a++ )
   {
    scanf( "%d" , &T[ i ][ a ] ) ;
    R = max( R , T[ i ][ a ] );
   }
   while( L < R )
   {
    int M =  L + ( R - L + 1 ) / 2 ;
    if( test( M ) )
     L = M ;
    else
     R = M - 1 ;
   }
   printf( "%d\n" , L ) ;
 }
 return 0;
}