Smile

重点：在于建图，建好图之后就一个纯裸的二分匹配。
知识：匈牙利算法 注意 最大独立集是集合的总元素个数减去最大二分匹配数
bug：此题无bug处，数据如果要符合实际情况，无法出特殊数据，要卡只能卡时间。

#include<cstdio>//此次建图是建的二分图，上面一篇文章是用的一个图求二分匹配。
#include<cstring>
#include<vector>
using namespace std;

#define max 510
int ch1[max][2];
int ch2[max][2];
int flag[max];
int vy[max];
int vx[max];
vector<int> p1[max];
int num1,num2;
int p,m,n;

void init()
{
     char a,b;
     int d,c;
     memset(p1,0,sizeof(p1));
     num1 = 0;
     num2 = 0;
     scanf("%d%d%d",&m,&n,&p);
     for( int i=1; i<=p; ++i )
     {
          getchar();
          scanf("%c%d %c%d",&a,&c,&b,&d);
          if( 'C' == a )
          {
             ch1[++num1][0] = c;
             ch1[num1][1] = d;
          }
          else
          {
              ch2[++num2][0] = c;
              ch2[num2][1] = d;
          }
     }
     for( int i=1; i<=num1; ++i )
         for( int j=1; j<=num2; ++j )
         {
              if( ch1[i][0] == ch2[j][1] || ch1[i][1] == ch2[j][0] )
              p1[i].push_back(j);
         }
         return ;
}

bool find(int i)//注意flag数组的赋值
{
     int num = p1[i].size();
     for( int j=0; j<num; ++j )
     {
          if( flag[ p1[i][j] ] == 0 )
          {
              flag[ p1[i][j] ] = 1;
              if( vy[ p1[i][j] ] == 0 || find( vy[ p1[i][j] ] ) )
              {
                  vx[i] = p1[i][j];
                  vy[ p1[i][j] ] = i;
                  return true;
              }
          }
   }
   return  false;
}

int main()
{
    int t;
    scanf("%d",&t);
    while( t-- )
    {
       init();
       int sig = 0;
       memset(vx,0,sizeof(vx));
       memset(vy,0,sizeof(vy));
       for( int i=1; i<=num1; ++i )
       {
            memset(flag,0,sizeof(flag));
            if( find(i) )
            {
                sig ++;
            }
       }
       printf("%d\n",p-sig);
    }
    return 0;
}