hdu 3829 Cat VS Dog【最大独立集】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/48340789

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

小朋友间建立互斥关系。
只有一个小朋友的集合，用拆点的思想，把每个小朋友拆成2个小朋友，这样在求最大匹配的时候除以2就可以了。就必须建立双向边，比如1和2之间有矛盾，建立1-2矛盾边，2-1矛盾边。

最大独立集 = 点数 - 最大匹配数。

代码：

#include <iostream>  
#include <algorithm>  
#include <set>  
#include <map>  
#include <string.h>  
#include <queue>  
#include <sstream>  
#include <stdio.h>  
#include <math.h>  
#include <stdlib.h>  

using namespace std;

int n, m, k;
int p[1000][1000];
int book[1000];
int match[1000];

int dfs(int u)
{
    int i;
    for (i = 1; i <= k; i++)
    {
        if (book[i] == 0 && p[u][i] == 1)
        {
            book[i] = 1;
            if (match[i] == 0 || dfs(match[i]))
            {
                match[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

struct stu
{
    string like;
    string dislike;
}st[1100];

int main()
{
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        int ans = 0;
        memset(match, 0, sizeof(match));
        memset(p, 0, sizeof(p));

        string u, v;
        for (int i = 1;i <= k;i++)
        {
            cin >> u >> v;  
            st[i].like = u;
            st[i].dislike = v;  
        }

        for (int i = 1;i <= k;i++)
            for (int j = 1;j <= k;j++)
            {
                if (st[i].like == st[j].dislike || st[i].dislike == st[j].like)
                    p[i][j]  = p[j][i] = 1;
            }

        for (int i = 1; i <= k; i++)
        {
            memset(book, 0, sizeof(book));
            if (dfs(i))
                ans++;
        }
        printf("%d\n", k - ans/2);
    }
    return 0;
}