HDU 2768. Cat vs. Dog

发表于 分类于

链接

http://acm.hdu.edu.cn/showproblem.php?pid=2768

题意

$n$ 个观众，每个观众都是一个爱猫的人（即讨厌狗）或一个爱狗的人（即一个讨厌猫）。

每个观众可以投票决定两件事：一只宠物保留，一只宠物扔掉。

挑选留下来的宠物，以便最大限度地满足观众。

思路

将每个观众和与其矛盾的观众连线，求二分图最大独立集。

代码

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=505;
int n,a,b,match[N];
bool f[N][N],st[N];
PII p[N];
bool dfs(int u) {
    for(int v=1;v<=n;v++) {
        if(!f[u][v]||st[v]) continue;
        st[v]=true;
        if(match[v]==-1||dfs(match[v])) {
            match[v]=u;
            match[u]=v;
            return true;
        }
    }
    return false;
}
int main() {
    //freopen("D:/Sublime Text 3/in.txt","r",stdin);
    int tt;
    scanf("%d",&tt);
    while(tt--) {
        scanf("%d%d%d",&a,&b,&n);
        for(int i=1;i<=n;i++) {
            char c;
            int d;
            scanf(" %c%d",&c,&d);
            p[i].FI=(c=='C'?d:d+a);
            scanf(" %c%d",&c,&d);
            p[i].SE=(c=='C'?d:d+a);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=false;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(p[i].FI==p[j].SE||p[i].SE==p[j].FI)
                    f[i][j]=f[j][i]=true;
        for(int i=1;i<=n;i++) match[i]=-1;
        int res=n;
        for(int i=1;i<=n;i++) {
            if(match[i]!=-1) continue;
            for(int j=1;j<=n;j++) st[j]=false;
            if(dfs(i)) res--;
        }
        printf("%d\n",res);
    }
    return 0;
}