hdu 2768

求最大留下的观众，观众之间存在不能同时满足的关系，就是矛盾关系，

矛盾关系建边，建边是双向的所以最大匹配要/2

还有一种建图的方法：把观众分成两个集合，一个是投留下猫的，一个是投留下狗的

每个集合间没有矛盾关系，就是二分图了，求出最大匹配，

两种方法都是要求最大独立集

#include
#include
#define N 510
int map[N][N],n,m,k,match[N],vis[N];
struct op
{
    int love,hate;
}p[N];
int find(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0&&map[x][i]==1)
        {
            vis[i]=1;
            if(match[i]==-1||find(match[i])==1)
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,sum,t,k;
    int a[2];
    char str[3];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&m,&k,&n);
        for(i=1;i<=n;i++)
        {
            for(j=0;j<2;j++)
            {
                scanf("%s",str);
                a[j]=0;
                if(str[0]=='D')
                {
                    for(k=1;str[k];k++)
                        a[j]=a[j]*10+str[k]-'0';
                    a[j]+=m;
                }
                else if(str[0]=='C')
                    for(k=1;str[k];k++)
                        a[j]=a[j]*10+str[k]-'0';
            }
            p[i].love=a[0];
            p[i].hate=a[1];
        }
        memset(map,0,sizeof(map));
        memset(match,-1,sizeof(match));
        sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j 
 
#include
#include
#define N 510
int map[N][N],n,m,k,match[N],vis[N],num1,num0;
struct op
{
    int cat,dog;
}p[2][N];
int find(int x)
{
    for(int i=1;i