Tyvj练习

Published: by Creative Commons Licence

  • Tags:

tyvj1338

我们为每个单元建立一个结点,之后将结点按照下标和的奇偶性分为两类。建立一个特殊的结点,表示类别2代表的单元权值之和,而类别1的结点表示选择该结点获得的收益,而类别2的结点表示不选择该结点的损失。而对于在原图相邻的第一类结点u和第二类结点v,建立一条有向边$(u,v)$,表示要在第一类结点中选择u,必须在第二类结点中移除v。之后我们要求的实际上是这个图的最大权闭合子图。