题解：UVA12168 Cat vs. Dog

做法

分析：

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

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

最大独立集结论：

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

代码怎么写：

将喜欢第

i

只猫（狗）的观众和讨厌第

i

只猫（狗）的观众连单向边即可，题目中

k

最大只有

500

，可以将每个观众的喜好存下来

n^2

枚举即可，具体细节可以参考下文代码。

代码

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

CPP

#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;
}

题外话

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

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

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

题解：UVA12168 Cat vs. Dog

文章操作

做法

分析：

代码怎么写：

代码

题外话

相关推荐

评论

题解：UVA12168 Cat vs. Dog