容易知道答案为原图的最大子二分图大小。
枚举每个点在二分图的左边还是右边，计算出答案。时间复杂度 \(O(2^n\times m)\)。
考虑递推构造方案。假设现在已经有了一组 \(n=2k-2\) 的方案，需要推到 \(n=2k\)。
对于原方案中的第 \(i\) 棵生成树，添上 \(2 i-1\leftrightarrow 2k-1\) 和 \(2i\leftrightarrow 2k\) 的边；同时令所有 \(2i\leftrightarrow 2k-1\) 和 \(2i-1\leftrightarrow 2k\) 的边构成一棵新的生成树。这样就构造出了符合题意的方案。
从 \(2k\) 推到 \(2k+1\) 时，对第 \(i\) 棵生成树添上 \(i\leftrightarrow 2k+1\) 即可。
时间复杂度 \(O(n^2)\)。
在图上对相邻的两个格子 \((x_1,y_1)\) 和 \((x_2,y_2)\)，连一条权值为 \(v_{x_1,y_1}\times v_{x_2,y_2}\) 的边，跑最大生成树就是答案。
考虑二分答案，check 的时候遍历整棵树，贪心地能拼就拼。时间复杂度 \(O(n\log n\log SIZE)\)。
标签：二分,1.12,题解,复杂度,生成,leftrightarrow,2i,模拟,2k From： https://www.cnblogs.com/Tarantula/p/1-12-p.html