hdu-2768-Cat vs. Dog(二分图-最大匹配数)

题意：

有猫C个和狗D个，有V个投票人，每个人喜欢猫讨厌狗或则喜欢狗讨厌猫！

求最多能满足多少投票人。

分析：

两个投票者矛盾的话就连一条边，总数减去最大匹配数/2就是要求的答案

// File Name: ACM/HDU/2768.cpp

// Author: Zlbing

// Created Time: 2013年08月16日 星期五 15时14分15秒

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=;

int Left[MAXN];//Left[i]为左边与右边第i个点匹配的编号

int w[MAXN][MAXN];

bool S[MAXN],T[MAXN];

int N;

bool match(int i)

{

    S[i]=true;

    for(int j=;j<=N;j++)if(w[i][j]&&!T[j])

    {

        T[j]=true;

        if(Left[j]==||match(Left[j]))

        {

            Left[j]=i;

            return true;

        }

    }

    return false;

}

int hungry(){

    CL(Left,);

    int sum=;

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

    {

        CL(S,);

        CL(T,);

        if(match(i))sum++;

    }

    return sum;

}

string A[MAXN],B[MAXN];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m,k;

        scanf("%d%d%d",&n,&m,&k);

        REP(i,,k)

            cin>>A[i]>>B[i];

        CL(w,);

        REP(i,,k)

            REP(j,i+,k)

            {

                if(A[i]==B[j]||B[i]==A[j])

                    {

                        w[i][j]=w[j][i]=;

                    }

            }

        N=k;

        int ans=k-hungry()/;

        printf("%d\n",ans);

    }

    return ;

}