CF1284G

题意

给定(n imes m)有障碍的网格图，如果((i,j))没有障碍将其看作一个点（保证((1,1))没有障碍）
两个相邻（四连通）没有障碍的点间有一条边
点有颜色，若(i+j)为奇数则((i,j))为白色，否则为黑色
求一棵生成树，使得叶子节点全部为白色（即使((1,1))度数为一，也不看作叶子节点）
(n,mle 20)

做法

将((1,1))看作白色

设拟阵(M_1(S,I))为图拟阵的对偶拟阵

设拟阵(M_2(S,I))，其中(S)为边集，(I={Psubseteq S：S删掉P后所有黑点度数ge 2})

容易证明这在黑点点集为独立集的任何无向图中均为拟阵

观察发现，可以将问题转化为求(M_1,M_2)的拟阵交问题