记录编号	394405	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]猫和狗	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2017-04-13 14:15:05	内存使用	24.20 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define N 2500
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
int match[N];
int flag[N],a[N][N];
int cat,dog,n;
struct haha
{
       char like[5];
       char dis[5];
}people[N];
bool find(int p)
{
     pos(i,1,n)
     {
        if(a[p][i]==1&&flag[i]==0)
        {
           flag[i]=1;
           if(match[i]==0||find(match[i]))
           {
             match[i]=p;
             return true;
           }
        }
     }
     return false;
}
int main()
{
    freopen("catdog.in","r",stdin);
    freopen("catdog.out","w",stdout);
    cin>>cat>>dog>>n;
    pos(i,1,n)
       cin>>people[i].like>>people[i].dis;
    pos(i,1,n)
      pos(j,1,n)
      {
         if(people[i].like[0]==people[j].dis[0]&&people[i].like[1]==people[j].dis[1]&&people[i].like[2]==people[j].dis[2]&&people[i].like[3]==people[j].dis[3])
         {
            a[i][j]=1;
            a[j][i]=1;
         }
      }
    int ans=0;
    pos(i,1,n)
    {
      memset(flag,0,sizeof(flag));
      if(find(i))
        ans++;
    }
    cout<<n-ans/2;
    //while(1);
    return 0;
}