HDU2768-二分图最大独立集

你的名字 2022-07-12 07:24 148阅读 0赞

# Cat vs. Dog #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 2113    Accepted Submission(s): 817**

Problem Description

The latest reality show has hit the TV: \`\`Cat vs. Dog''. In this show, a bunch of cats and dogs compete for the very prestigious Best Pet Ever title. In each episode, the cats and dogs get to show themselves off, after which the viewers vote on which pets should stay and which should be forced to leave the show.  
  
Each viewer gets to cast a vote on two things: one pet which should be kept on the show, and one pet which should be thrown out. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog.  
  
Ingenious as they are, the producers have decided to use an advancement procedure which guarantees that as many viewers as possible will continue watching the show: the pets that get to stay will be chosen so as to maximize the number of viewers who get both their opinions satisfied. Write a program to calculate this maximum number of viewers.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:  
  
\* One line with three integers c, d, v (1 ≤ c, d ≤ 100 and 0 ≤ v ≤ 500): the number of cats, dogs, and voters.  
\* v lines with two pet identifiers each. The first is the pet that this voter wants to keep, the second is the pet that this voter wants to throw out. A pet identifier starts with one of the characters \`C' or \`D', indicating whether the pet is a cat or dog, respectively. The remaining part of the identifier is an integer giving the number of the pet (between 1 and c for cats, and between 1 and d for dogs). So for instance, \`\`D42'' indicates dog number 42.

Output

Per testcase:  
  
\* One line with the maximum possible number of satisfied voters for the show.

Sample Input

2
    1 1 2
    C1 D1
    D1 C1
    1 2 4
    C1 D1
    C1 D1
    C1 D2
    D2 C1

Sample Output

1
    3

**题目大意：**

给你n只猫和m条狗，编号分别为1-n和1-m，然后有一场演出由一只猫和一条狗组成，有k个观众，他们希望哪一个应该出演，不希望看到哪一个出演，具体见题目描述，问怎么安排演出才能满足大多数的观众并输出最多的满足的观众数

**题目思路：**

刚开始看到时没有啥思路，然后想想题目要求最多的观众，如果我们猫和狗为集合建立二分图的话，最后得到的是猫和狗的最大匹配而不是最多满足的观众数，所以我们换着方式，以观众为集合建立二分图，然后我们考虑如何来建图，首先每个观众有自己喜欢的和不喜欢的，如果两个观众一个喜欢猫1一个不喜欢猫1或者是一个不喜欢狗1一个喜欢狗1，那么必然这两个观众的观点存在矛盾，他们两个只能满足一个，既然这样，我们就很好想到让有矛盾的观众连边，这样最后就转换成求最大独立集了！

**AC代码：**

#include<cstring>
    #include<cstdio>
    
    const int maxn = 1005;
    
    bool vis[maxn],mp[maxn][maxn];
    int link[maxn];
    int n,m,k;
    
    bool dfs(int u){
        for(int i=1;i<=k;i++){
            if(!vis[i]&&mp[u][i]){
                vis[i]=true;
                if(link[i]==-1||dfs(link[i])){
                    link[i]=u;
                    return true;
                }
            }
        }
        return false;
    }
    
    int main()
    {
        int t;scanf("%d",&t);
        while(t--){
            scanf("%d%d%d",&n,&m,&k);
            memset(link,-1,sizeof(link));
            memset(mp,false,sizeof(mp));
            int num1[1005],num2[1005];
            char s1[1005][10],s2[1005][10];
            for(int j=1;j<=k;j++){
                scanf("%s %s",s1[j],s2[j]);
                num1[j]=0,num2[j]=0;
                int i=1;
                while(s1[j][i])num1[j]=num1[j]*10+s1[j][i]-'0',i++;
                i=1;
                while(s2[j][i])num2[j]=num2[j]*10 +s2[j][i]-'0',i++;
                for(int l=1;l<j;l++){
                    if(num1[l]==num2[j]&&s1[l][0]==s2[j][0]||num2[l]==num1[j]&&s2[l][0]==s1[j][0])
                        mp[l][j]=mp[j][l]=true;
                }
            }
            int ans = 0;
            for(int i=1;i<=k;i++){
                memset(vis,false,sizeof(vis));
                if(dfs(i))ans++;
            }
            printf("%d\n",k-ans/2);
        }
        return 0;
    }