HDU - 3829 二分图的最大独立集

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


思路：如果A喜欢==B不喜欢||A不喜欢==B喜欢。那么A和B不能同时满足。连一条边。因为如果孩子的喜欢动物是猫，那么他/她的不喜欢动物一定是狗，反之亦然。那么可以证明一定一个二分图。就是求二分图的最大独立集。

#include  <map>
#include  <set>
#include  <cmath>
#include  <queue>
#include  <cstdio>
#include  <vector>
#include  <climits>
#include  <cstring>
#include  <cstdlib>
#include  <iostream>
#include  <algorithm>
#define LL long long
using namespace std;

const int INF=1e9;
const int maxn=505;// 最大点数
vector<int> G[maxn];
int Mx[maxn],My[maxn],Nx,Ny;//Mx[i]表示左集合i顶点所匹配的右集合的顶点序号
int dx[maxn],dy[maxn],dis;//My[i]表示右集合i顶点所匹配的左集合的顶点序号
bool vis[maxn];

 //寻找 增广路径集
bool searchP(){
    queue<int> q;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(int i=1;i<=Nx;i++){
        if(Mx[i]==-1){
            q.push(i);dx[i]=0;
        }
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        if(dx[u]>dis) break;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(dy[v]==-1){
                dy[v]=dx[u]+1;
                if(My[v]==-1) dis=dy[v];
                else{
                    dx[My[v]]=dy[v]+1;
                    q.push(My[v]);
                }
            }
        }
    }
    return dis!=INF;
}
//寻找路径 深度搜索
bool dfs(int u){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!vis[v]&&dy[v]==dx[u]+1){
            vis[v]=1;
            if(My[v]!=-1&&dy[v]==dis) continue;
            if(My[v]==-1||dfs(My[v])){
                My[v]=u;
                Mx[u]=v;
                return true;
            }
        }
    }
    return false;
}
//得到最大匹配的数目
int MaxMatch(){
    int res=0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(searchP()){
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=Nx;i++){
            if(Mx[i]==-1&&dfs(i)) res++;
        }
    }
    return res;
}

string s1[505], s2[505];
int main(){
    int n1, n2, n3;
    string a, b;
    while(~scanf("%d%d%d", &n1, &n2, &n3)){
        for(int i=1; i<=n3; i++){
            cin>>a>>b;
            s1[i]=a;
            s2[i]=b;
        }
        for(int i=1; i<=n3; i++){
            for(int j=i+1; j<=n3; j++){
                if(s1[i]==s2[j]||s2[i]==s1[j]){
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        }
        Nx=Ny=n3;
        printf("%d\n", n3-MaxMatch()/2);
        for(int i=1; i<=n3; i++) G[i].clear();
    }

    return 0;
}