「HDU-3829」Cat VS Dog (最大团)

发表于 | 分类于 ，

「HDU3829」Cat VS Dog
二分图匹配，最大团问题

题意

对于p个儿童，每个儿童有其喜欢的动物和讨厌的动物，如果一个儿童喜欢的动物没有被移除，并且讨厌的动物被移除，他/她将会很快乐。求能达到的最大快乐儿童数量。

思路

对于每个儿童，如果儿童a喜欢的动物是b讨厌的动物，或者a讨厌的动物是b喜欢的动物，那么a,b存在冲突，即不能同时选择a,b；

对不存在冲突的a,b连边，那么对于n个儿童，如果他们之间两两相连（即都不存在冲突），则可以同时选择这些儿童。

解法

二分图的最大独立集

定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
方法：最大独立集=所有顶点数-最小顶点覆盖

二分图的最大团

定义：对于一个二分图，我们在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。
方法：二分图的最大团=补图的最大独立集

建立二分图，对不存在冲突的点连边，求解最大团即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=500+10;

int p;
int edge[maxn][maxn];
int linker[maxn];
bool vis[maxn];

bool path(int u)
{
    for(int v=1;v<=p;v++)
    {
        if(edge[u][v]&&!vis[v])
        {
            vis[v]=true;
            if(linker[v]==-1||path(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int res=0;
    memset(linker,0xff,sizeof(linker));
    for(int i=1;i<=p;i++)
    {
            memset(vis,false,sizeof(vis));
            res+=path(i);
    }
    return res;
}

int main()
{
    int n,m;
    char like[510][20],hate[510][20];
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        for(int i=1;i<=p;i++)
        {
            scanf("%s%s",like[i],hate[i]);
        }
        memset(edge,1,sizeof(edge));
        for(int i=1;i<=p;i++)
        {
            for(int j=1;j<=p;j++)
            {
                if(strcmp(like[i],hate[j])!=0&&strcmp(like[j],hate[i])!=0) 
                    edge[i][j]=0;
            }
        }
        printf("%d\n",(2*p-hungary())/2);
    }
    return 0;
}