poj2771

题解：

二分图最大独立及

每两个不能选的渐变

输出n+m-最大匹配

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

int ne[N*N],num,fi[N],x,T,zz[N*N],n,m,f[N],match[N],a[N],b[N],cnt1,cnt2;

char s1[N][N],s[N],s2[N][N],m1[N][N],m2[N][N];

void jb(int x,int y)

{

    ne[++num]=fi[x];

    fi[x]=num;

    zz[num]=y;

}

int dfs(int x)

{

    for (int i=fi[x];i;i=ne[i])

     if (!f[zz[i]])

      {

          f[zz[i]]=;

          if (!match[zz[i]]||dfs(match[zz[i]]))

           {

               match[zz[i]]=x;

               return ;

           }

      }

    return ;

}

int pd(char s1[],char s2[])

{

    if (strlen(s1)!=strlen(s2))return ;

    for (int i=;s1[i];i++)

     if (s1[i]!=s2[i])return ;

    return ;

}

int main()

{

    scanf("%d",&T);

    while (T--)

     {

         memset(match,,sizeof match);

         memset(fi,,sizeof fi);

         num=cnt1=cnt2=;

         scanf("%d",&n);

         for (int i=;i<=n;i++)

          {

              scanf("%d%s",&x,&s);

              if (s[]=='F')

               {

                   a[++cnt1]=x;

                   scanf("%s%s",&m1[cnt1],&s1[cnt1]);

               }

              else

             {

                 b[++cnt2]=x;

                 scanf("%s%s",&m2[cnt2],s2[cnt2]);

             }

          }

         for (int i=;i<=cnt1;i++)

          for (int j=;j<=cnt2;j++)

           if (abs(a[i]-b[j])<=&&pd(m1[i],m2[j])&&!pd(s1[i],s2[j]))jb(i,j);

         int ans=;

        for (int i=;i<=n;i++)

         {

             memset(f,,sizeof f);

             ans+=dfs(i);

         }

        printf("%d\n",n+m-ans);

     }

}