题解：UVA12168 Cat vs. Dog

· · 题解

做法

分析：

此题将所有观众分为了喜欢猫讨厌狗和喜欢狗讨厌猫的两个集合，两个集合内部不发生冲突所以我们可以往二分图上想。

再看此题要我们求出最多能留下多少观众，发现可以去跑最大独立集求解。

最大独立集结论：

最大独立集=顶点数-二分图的最大匹配数

代码怎么写：

将喜欢第 i 只猫（狗）的观众和讨厌第 i 只猫（狗）的观众连单向边即可，题目中 k 最大只有 500，可以将每个观众的喜好存下来 n^2 枚举即可，具体细节可以参考下文代码。

代码

注：由于本蒟蒻并没有 UVA 的号所以无法验证代码的正确性，仅供参考。

#include<cstdio>
#include<iostream>
using namespace std;
int len;
int n,m,k;
string a[505],b[505];
int num[300005],pre[300005],last[505],cnt;
int t[505],link[505];
int poi;
int ans;
void ddxyz(){
    ans=cnt=0;
    for(int i=1;i<=500;i++){
        link[i]=last[i]=0;
    }
}
void add(long long x,long long y){
    ++cnt;
    num[cnt]=y;
    pre[cnt]=last[x];
    last[x]=cnt;
}
bool find(int xy){
    for(int i=last[xy];i;i=pre[i]){
        if(t[num[i]]!=poi){
            t[num[i]]=poi;
            if(link[num[i]]==0||find(link[num[i]])){
                link[num[i]]=xy;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>len;
    while(len--){
        ddxyz();
        cin>>n>>m>>k;
        for(int i=1;i<=k;i++){
            cin>>a[i]>>b[i];
            a[i]=' '+a[i];
            b[i]=' '+b[i];
            //这里参考了yzh_Error404大佬题解里的写法直接通过字符串进行比较，仔细想一下发现是可行的 
        }
        for(int i=1;i<=k;i++){
            for(int j=1;j<=k;j++){
                if(i==j){
                    continue;   
                }
                if(a[i]==b[j]||a[j]==b[i]){
                    if(a[i][1]=='C'){
                        add(i,j);
                    }
                    else{
                        add(j,i);
                    }
                    //喜欢猫的向讨厌猫的连边 
                }
            }
        }
        for(int i=1;i<=k;i++){
            ++poi;
            if(find(i)){
                ans++;
            }
        }
        cout<<k-ans<<endl;
    }
    return 0;
}

题外话

此题难在发现它是在求最大独立集和建边操作，本蒟蒻也是看了大佬们的题解才知道思路的。相信大家多多刷题一定可以培养出这方面的思维。

附上一些关于二分图的结论，希望能帮到大家：

广告：二分图相关详解，大家对上述概念不清晰的也可以去看一下