hdu3829

题解：

对于每一个孩子裂点+建边

如果i孩子讨厌的和j孩子喜欢的相同，那么建边

然后跑最大独立集

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2005;
int fi[N],num,s1[N],s2[N],match[N],zz[N*N],ne[N*N],n,f[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]]=1;
          if (!match[zz[i]]||dfs(match[zz[i]]))
           {
               match[zz[i]]=x;
               return 1;
           }
      }
    return 0;  
}
int read()
{
    int k=0,x=0;char c;
    for (c=getchar();c!='C'&&c!='D';c=getchar());
    if (c=='C')k+=n;
    scanf("%d",&x);
    return k+x;
}
int main()
{
    while (~scanf("%d%d%d",&n,&n,&n))
     {
         memset(fi,0,sizeof fi);
         memset(match,0,sizeof match);
        num=0;
        for (int i=1;i<=n;i++)s1[i]=read(),s2[i]=read();
        for (int i=1;i<=n;i++)
         for (int j=1;j<=n;j++)
          if (s1[i]==s2[j]||s2[i]==s1[j])jb(i,j);
        int ans=0;
        for (int i=1;i<=n;i++)
         {
             memset(f,0,sizeof f);
             ans+=dfs(i);
         }  
        printf("%d
",n-ans/2); 
     }
}