Code Names 网络流 + 二分图

Code Names 网络流 + 二分图

题目大意:

给你N个单词,这n个单词都是由相同的字符组成但是顺序不一致,没有任意两个单词是一样的,定义一种特殊的一对单词, ((x,y)) 只需要 x 单词内部交换一次任意两个字符就可以变成y。求一个集合满足没有特殊单词对的最大集合是的单词数是多少。

题解:

  • 首先很自然的可以想到建图,所以就转化成图论问题了
  • 如果特殊单词对建边,那么就是求最大独立子集,如果是非特殊单词对建边,也就是之前的补图,那么就是求最大完全子图。
  • 我们会求二分图的最大独立子集,又因为每次是只有两个位置不一致,而且可以交换获得,那么可以证明的是不会出现奇环,然后又可以知道的是 偶数环可以转化成二分图,所以直接用二分图的求解方法求解。

代码以后再补。。。

原文地址:https://www.cnblogs.com/EchoZQN/p/14508878.html