【HDU】4115 Eliminate the Conflict 2-sat

admin管理员组

文章数量:1596345

传送门：【HDU】4115 Eliminate the Conflict

题目分析：这道2-sat略恶心啊。。

用了比较直观的建图方法，大概一看就能懂。

设石头(R)，布(P)，剪刀(S)。

由于每一把出了一种手势以后便不能出其他的了，所以建边：

< R , ~P > , < R , ~S > , < P , ~R > , < P , ~S > , < S , ~R > , < S , ~P >

由于每一把至少要么平局要么胜，假设对方出石头(R)，建边：

< ~P , S > , < ~S , P >

接下来如果限制第 i 盘与第 j 盘出的必须相同，建边：

< Ri , Rj > , < Rj , Ri > , < Pi , Pj > , < Pj , Pi > , < Si , Sj > , < Sj , Si >

同样如果要求必须不同，建边：

< Ri , ~Rj > , < Rj , ~Ri > , < Pi , ~Pj > , < Pj , ~Pi > , < Si , ~Sj > , < Sj , ~ Si >

最后跑一遍2-sat就能得到答案。感觉就是约束要多一些，其他和平时的差不多。

代码如下：

#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 )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 60000 ;
const int MAXE = 200000 ;

struct Edge {
	int v ;
	Edge* next ;
} E[MAXE] , *H[MAXN] , *cur ;

int dfn[MAXN] , low[MAXN] , scc[MAXN] , scc_cnt ;
int S[MAXN] , top , dfs_clock ;
int n , m ;

void init () {
	cur = E ;
	top = scc_cnt = dfs_clock = 0 ;
	CLR ( H , 0 ) ;
	CLR ( dfn , 0 ) ;
	CLR ( scc , 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 ( low[u] == dfn[u] ) {
		++ scc_cnt ;
		do {
			scc[S[-- top]] = scc_cnt ;
		} while ( u != S[top] ) ;
	}
}

int ok () {
	REP ( i , 0 , n * 6 ) if ( !dfn[i] ) tarjan ( i ) ;
	REP ( i , 0 , n * 3 ) if ( scc[i << 1] == scc[i << 1 | 1] ) return 0 ;
	return 1 ;
}

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' ;
}

void solve () {
	int x , i , j ;
	init () ;
	scanf ( n ) ;
	scanf ( m ) ;
	REP ( o , 0 , n ) {
		scanf ( x ) ;
		int a = x - 1 ;
		int b = x % 3 ;
		addedge ( o * 6 + ( a << 1 | 1 ) , o * 6 + ( b << 1 ) ) ;
		addedge ( o * 6 + ( b << 1 | 1 ) , o * 6 + ( a << 1 ) ) ;
		addedge ( o * 6 + 0 , o * 6 + 3 ) ;
		addedge ( o * 6 + 0 , o * 6 + 5 ) ;
		addedge ( o * 6 + 2 , o * 6 + 1 ) ;
		addedge ( o * 6 + 2 , o * 6 + 5 ) ;
		addedge ( o * 6 + 4 , o * 6 + 1 ) ;
		addedge ( o * 6 + 4 , o * 6 + 3 ) ;
	}
	while ( m -- ) {
		scanf ( i ) ;
		scanf ( j ) ;
		scanf ( x ) ;
		-- i , -- j ;
		addedge ( i * 6 + 0 , j * 6 + 0 + x ) ;
		addedge ( i * 6 + 2 , j * 6 + 2 + x ) ;
		addedge ( i * 6 + 4 , j * 6 + 4 + x ) ;
		addedge ( j * 6 + 0 , i * 6 + 0 + x ) ;
		addedge ( j * 6 + 2 , i * 6 + 2 + x ) ;
		addedge ( j * 6 + 4 , i * 6 + 4 + x ) ;
	}
	printf ( ok () ? "yes\n" : "no\n" ) ;
}
	
int main () {
	int T , cas = 0 ;
	scanf ( T ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}

本文标签： hduEliminateSatconflict