朝田诗乃 的博客

朝田诗乃 的博客

题解 P5030 【长脖子鹿放置】

posted on 2018-11-14 07:49:38 | under 题解 |

对于10%的数据,枚举每个格子放或不放,复杂度O(2^(n^2)).

对于80%的数据,可以观察到,白格上的长脖子鹿只能跳到白格,黑格上的长脖子鹿只能跳到黑格,因此我们把黑、白格子分开考虑。若两个格子是“目”字的对角(能互相攻击到),则在他们对应的节点之间连边。容易发现,我们连出来的图中不存在奇环。因此,我们建出的图确实是一张二分图。

求上述二分图的最大独立集即可。

对于100%的数据,出题人在说明中说过考虑图的遍历顺序对效率影响。考虑匈牙利算法的实现过程,若当前点找到的匹配边是暂时没有匹配冲突,那么就可以直接匹配结束dfs,否则将进行复杂的增广。因此,从(x+3,x-1)开始(即下偏左)从下往上遍历可以减少冲突的概率,(上方的可匹配点被之前的点匹配的可能性较高。),可以将复杂度降为O(能过)。

标程提供:朝田诗乃/X。