这道题目有个很显然的二分图就是将猫和狗分开，但是你会发现这样根本做不出来题目，所以我们考虑更扩展的东西
这道题目要我们求最多的客户，我们最开始是把客户当成边，跑最大匹配，发现不行，所以我们现在尝试把客户当成点
想到什么？对，就是最大独立集
于是，我们考虑如何建图
回想一下独立集：任意两点没有边相连
于是在这道题目，两点之间连边肯定就代表着这两点不能同时选，即这两个顾客冲突了
那要怎么样才能冲突呢？不难想到，若某只猫/狗被选/不选，那么其所牵涉的顾客是有冲突的
于是，我们将喜欢某只猫/狗的人和不喜欢这只猫/狗的人连边，这就是矛盾的信息
由于一般无向图的最大独立集是NP-hard问题，所以我们还要证明这是一个二分图
这个时候就要利用题目条件了：注意到每个观众都是更喜欢猫或更喜欢狗，所以两个空后面一定会被勾上不同的内容。喜欢猫的观众会在第一空后面选择猫，第二空后面选择狗；反之就会在第一空后面选择狗，第二空后面选择猫
这也就是说，如果我们把所有喜欢猫的人放在一边，那么这些人一定是不喜欢狗的；如果我们把所有喜欢狗的人放在一边，那么这些人一定是不喜欢猫的；所以原来的图被分成了两部分，即是二分图
至此，题目解决
标签：,二分,题目,后面,喜欢,这道,我们 From： https://www.cnblogs.com/dingxingdi/p/18014244