题目分析:本题,如果某个人i喜欢的动物与另一个人j讨厌的动物相同或者i讨厌的动物与j喜欢的动物相同,那么就对这两个人建边,表示只满足其中一个人。因为条件是对称的,所以如果有边( i , j ),那么一定会有边( j , i )。因为我们要求满足最多的人两两之间没有矛盾关系,那么也就是说我们要求最大独立集,因为最大独立集=顶点数-最大匹配数,又因为顶点数以及最大匹配数都翻倍了,所以最终答案除以二。
代码如下:
#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 = 505 ; const int MAXQ = 505 ; const int MAXE = 1000000 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , n ; Edge () {} Edge ( int v , int n ) : v ( v ) , n ( n ) {} } E[MAXE] ; int H[MAXN] , cntE ; int dx[MAXN] , dy[MAXN] ; int Lx[MAXN] , Ly[MAXN] ; int Q[MAXQ] , head , tail ; int vis[MAXN] ; int dis ; int n , m , p ; int a[MAXN] , b[MAXN] ; void init () { cntE = 0 ; CLR ( H , -1 ) ; } void addedge ( int u , int v ) { E[cntE] = Edge ( v , H[u] ) ; H[u] = cntE ++ ; } int Hopcroft_Karp () { dis = INF ; head = tail = 0 ; CLR ( dx , -1 ) ; CLR ( dy , -1 ) ; FOR ( i , 1 , p ) if ( Lx[i] == -1 ) { Q[tail ++] = i ; dx[i] = 0 ; } while ( head != tail ) { int u = Q[head ++] ; if ( dx[u] >= dis ) continue ; for ( int i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( dy[v] == -1 ) { dy[v] = dx[u] + 1 ; if ( Ly[v] == -1 ) dis = dy[v] ; else { dx[Ly[v]] = dy[v] + 1 ; Q[tail ++] = Ly[v] ; } } } } return dis != INF ; } int hungary ( int u ) { for ( int i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( !vis[v] && dy[v] == dx[u] + 1 ) { vis[v] = 1 ; if ( ~Ly[v] && dy[v] == dis ) continue ; if ( Ly[v] == -1 || hungary ( Ly[v] ) ) { Lx[u] = v ; Ly[v] = u ; return 1 ; } } } return 0 ; } int match () { int res = 0 ; CLR ( Lx , -1 ) ; CLR ( Ly , -1 ) ; while ( Hopcroft_Karp () ) { CLR ( vis , 0 ) ; FOR ( i , 1 , p ) if ( Lx[i] == -1 ) res += hungary ( i ) ; } return res ; } void solve () { char ch ; int u , v ; init () ; scanf ( "%d%d%d" , &n , &m , &p ) ; FOR ( i , 1 , p ) { scanf ( " %c%d %*c%d" , &ch , &u , &v ) ; if ( ch == 'C' ) { a[i] = u ; b[i] = v + n ; } else { a[i] = u + n ; b[i] = v ; } } FOR ( i , 1 , p ) FOR ( j , 1 , p ) if ( a[i] == b[j] || a[j] == b[i] ) addedge ( i , j ) ; printf ( "%d\n" , p - match () / 2 ) ; } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) solve () ; return 0 ; }