题目分析:
二分能到达的深度。设对于第i层,a表示x[a[i]]取0,~a表示x[a[i]]取1,b同理。
然后按冲突建边:
c = 0 : < a , ~b > , < b , ~a >,不能同时取0
c = 1 : < a , b > , < ~b , ~a > , < b , a > , < ~a , ~b >,a、b必须取相同
c = 2 : < ~a , b > , < ~b , a >,不能同时取1
代码如下:
#include <cmath> #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 = 400 ; const int MAXE = 40000 ; struct Edge { int v ; Edge* next ; } ; struct Line { int x , y , c ; } ; Edge E[MAXE] , *H[MAXN] , *cur ; int dfn[MAXN] , low[MAXN] , scc[MAXN] , scc_cnt ; int S[MAXN] , top , dfs_clock ; int n , m ; Line l[MAXE] ; void init () { cur = E ; top = 0 ; scc_cnt = 0 ; 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] ) ; } } 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' ; } bool ok () { REP ( i , 0 , n << 1 ) if ( !dfn[i] ) tarjan ( i ) ; REP ( i , 0 , n ) if ( scc[i << 1] == scc[i << 1 | 1] ) return 0 ; return 1 ; } void solve () { scanf ( "%d%d" , &n , &m ) ; REP ( i , 0 , m ) scanf ( l[i].x ) , scanf ( l[i].y ) , scanf ( l[i].c ) ; int low = 0 , high = m ; while ( low < high ) { int mid = ( low + high + 1 ) >> 1 ; init () ; REP ( i , 0 , mid ) { if ( l[i].c == 0 ) { addedge ( l[i].x << 1 , l[i].y << 1 | 1 ) ; addedge ( l[i].y << 1 , l[i].x << 1 | 1 ) ; } else if ( l[i].c == 1 ) { addedge ( l[i].x << 1 , l[i].y << 1 ) ; addedge ( l[i].y << 1 , l[i].x << 1 ) ; addedge ( l[i].x << 1 | 1 , l[i].y << 1 | 1 ) ; addedge ( l[i].y << 1 | 1 , l[i].x << 1 | 1 ) ; } else { addedge ( l[i].x << 1 | 1 , l[i].y << 1 ) ; addedge ( l[i].y << 1 | 1 , l[i].x << 1 ) ; } } if ( ok () ) low = mid ; else high = mid - 1 ; } printf ( "%d\n" , low ) ; } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) solve () ; return 0 ; }