一个比较简单的图论问题,总算是填了这个小坑

Problem

有一些集合,每个集合中有且仅有两个元素,且不能同时选取两个元素,集合间的元素存在一定的选择关系,求解可行性及可行方案

Algorithm

其实这也不算是一个算法,就是一个很简单的图论模型,特别详细的过程可以看这里

把每个点拆成两种状态aaaa',状态之间互相连形如如果选a则必须选b的有向边,通过tarjan求强连通分量来判断可行性

算法流程如下:

  • 连边

  • 跑tarjan

  • 判可行性:判断一个点的两种状态是否同属一个强连通分量

  • 输出方案:输出两种状态中较先被缩成强连通分量的那个状态即可

    这个本质是对强连通分量进行缩点,缩完后形成的树(或者说是DAG也行)上显然如果状态xx被选,那么xx的子树的所有状态都要选。于是对于同一个点的两种状态而言,肯定只能选深度较深的那种状态,这种状态显然在用tarjan缩点时会先被缩起来

Connection

关于连边,主要思想就一个:选了a必选b对应连边aba\rightarrow bbab' \rightarrow a'逆否命题,必须也要连),然后根据相应的逻辑关系进行连边

常见的逻辑关系有:

  • aabb不能同时选:选了aa就要选bb',选了bb就要选aa'
  • aabb必须同时选:选了aa就要选bb,选了bb就要选aa,选了aa'就要选bb',选了bb'就要选aa'

  • aabb必须选一个:选了aa就要选bb',选了bb就要选aa',选了aa'就要选bb,选了bb'就要选aa

  • aa必须选:aaa'\rightarrow a

  • aa必须不选:aaa\rightarrow a'

Example

懒的放了