HDU3829-Cat VS Dog(最大独立集)

题目链接:HDU3829-Cat VS Dog

题意:

有n只狗,m只猫,p个人,每个人有一个喜爱的动物和一个讨厌的动物,若喜欢的动物是猫,那么讨厌的动物一定是狗,反之亦然,对一个人而言,若只有他喜爱的动物,没有他讨厌的动物,他就是快乐的,问任意移除一些动物后,最多的快乐人数。

题解:

首先考虑建图, 如果a喜欢的动物是b讨厌的动物,那么他俩中最多只有一个人能高兴,所以我们就这样建图:若a喜欢的和b讨厌的相同,那么他俩之间建一条边,然后求最大独立集即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
int n, m, p;
bool used[509];
int match[509];
struct EDGE
{
    int v, nxt;
} edge[509 * 509];
int cnt = 0, fir[509];
void addedge(int u, int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
bool dfs(int u)
{
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (!used[v])
        {
            used[v] = 1;
            if (match[v] == -1 || dfs(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int sum = 0;
    memset(match, -1, sizeof(match));
    for (int i = 1; i <= p; i++)
    {
        memset(used, 0, sizeof(used));
        if (dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    while (cin >> n >> m >> p)
    {
        cnt = 0;
        memset(fir, -1, sizeof(fir));
        string str1[509], str2[509];
        for (int i = 1; i <= p; i++)
            cin >> str1[i] >> str2[i];
        for (int i = 1; i <= p; i++)
            for (int j = 1; j <= p; j++)
            {
                if (str1[i] == str2[j])
                {
                    addedge(i, j);
                    addedge(j, i);
                }
            }
        int ans = MaxMatch();
        cout << p - ans / 2 << "\n";
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。