Petrozavodsk Winter-2019. 300iq Contest 1

Contest Info

date: 2019.05.15 10:30-15:30

practice link

Solutions

A. Angle Beats

题目大意

给出一个\(2\le n\le100\)\(2\le m\le100\)列的网格,每个格子要么是一个+,要么是一个*,要么是一个.。可以不重叠地放置一些\(I\)形或\(L\)形的由\(3\)个连通的格子组成的骨牌,要求\(I\)形的中心格子必须是+,另外两个格子必须是.\(L\)形的中心格子必须是*+,另外两个格子必须是.。问最多可以放下多少块骨牌,输出方案。

题解:相当于是一个二分图的\(V\)形最大匹配问题,*+是左部顶点,.是右部顶点,*+向其邻居的.连边,*要同时匹配其水平和竖直方向各一个邻居.+要同时匹配其任意两个邻居.。拆点转化为一般图最大匹配问题:*拆成两个点,其中一个向水平方向的邻居.连边,另一个向竖直方向的邻居.连边;+成两个点,两个点都向其所有邻居.连边;同一个点拆成的两个点连一条边。对于原图中的*+只有拆出来两个点都有不同的匹配点时贡献答案。带花树算法在一般图上的上界是\(O(n^3)\),但这个建模应该有更低的上界,可以通过。