CF1284G Seollal【拟阵交】
CF1284G Seollal【拟阵交】
给定 n×m 的网格图挖掉一些点,构造黑白染色时除 (1,1) 之外的叶子都与 (1,1) 不同色的生成树。
100 组 n,m≤10 或 1 组 n,m≤20。保证有解。
这是一份拟阵交板子。
构造两个拟阵 M1:无环,M2:除 (1,1) 之外的黑色点度数 ≤2。
求个拟阵交,如果有除 (1,1) 外的黑色点度数 <2 则无解。否则可以随便加一些边变成一棵生成树。
然后对着算法流程搞就完事了。
来源https://www.cnblogs.com/AThousandMoons/p/14825400.html