链接：http://acm.hdu.edu.cn/showproblem.php?pid=3829

题意：动物园有n条狗。m头猫。p个小孩，每一个小孩有一个喜欢的动物和讨厌的动物。如今动物园要转移一些动物。假设一个小孩喜欢的动物在，不喜欢的动物不在，他就会happy。问动物最多能使几个小孩happy。

思路：一个比較明显的二分图，不能以猫狗为顶点，那样找到的是哪些动物会转移，以小孩为顶点，找出最大点独立集，有两种建图方式，一种是以小孩总数p为左右点集的顶点个数，假设小孩a喜欢的动物是小孩b不喜欢的动物，就连一条边edge(a,b)；另外一种是以喜欢猫的小孩总数为左顶点个数。喜欢狗的为右顶点。依据矛盾连边。

这样两种仅仅是顶点数目不同。然后找二分图最大点独立集

二分图最大点独立集 = 顶点数 - 最大匹配数

只是第一种建图左右顶点数都是p。也就是每一个小孩在左右都有出现，总共出现两次。所以找到最大点独立集后除以2就是答案。

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 500010

#define eps 1e-7

#define INF 0x3F3F3F3F      //0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 1313131

#define MOD 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct node{

    int v,next;

}edge[MAXN];

int head[510],vis[510],dx[510],dy[510];

int cnt,n1,n2;  //n1左边的点数。n2右边的点数

void add_edge(int a,int b){

    edge[cnt].v = b;

    edge[cnt].next = head[a];

    head[a] = cnt++;

}

int path(int u){

    int i, j;

    for(i=head[u];i!=-1;i=edge[i].next){

        int v = edge[i].v;

        if(!vis[v]){

            vis[v] = 1;

            if(dy[v] == -1 || path(dy[v])){

                dx[u] = v;

                dy[v] = u;

                return 1;

            }

        }

    }

    return 0;

}

int maxmatch(){

    int i, j;

    int res = 0;

    memset(dx,-1,sizeof(dx));

    memset(dy,-1,sizeof(dy));

    for(i=1;i<=n1;i++){

        if(dx[i]==-1){

            memset(vis,0,sizeof(vis));

            res += path(i);

        }

    }

    return res;

}

struct Node{

    string like,dislike;

}animal[505];

int main(){

    int n,m,p,i,j;

    while(scanf("%d%d%d",&n,&m,&p)!=EOF){

        cnt = 0;

        memset(head,-1,sizeof(head));

        for(i = 0; i < p; i++){

            cin>>animal[i].like>>animal[i].dislike;

        }

        n1 = p;

        for(i = 0; i < p; i++){

            for(j = 0; j < p; j++){

                if(animal[i].like == animal[j].dislike || animal[i].dislike == animal[j].like){

                    add_edge(i + 1, j + 1);

                }

            }

        }

        int ans = maxmatch();

        printf("%d\n", (2 * p - ans) / 2);

    }

    return 0;

}