Starry Night Camping
Solution
sb题,可以发现如果不合法一定是存在路径类似于 \((1,1)\to (1,0)\to (0,0)\to (0,1)\) (模 \(2\) 意义下的),那么我们直接每个点拆开,两个点之间连边为点权,然后不同层之间相邻的连边直接跑最小割就好了。
[CQOI2017]老C的方块
Solution
也很蠢,跟上面的差不多。按下图编号即可。
可以发现不合法路径一定可以表示为 \(1\to 2\to 3\to 4\) 的,所以跟上面一样拆点跑最小割即可。
CF1288F Red-Blue Graph
Solution
我们发现红点可以理解为红边-蓝边 \(\ge 1\),蓝点可以理解为蓝边-红边 \(\ge 1\)。那么我们把红边、蓝边都理解为流,假设红边为出边,蓝边为入边,那么红点即是入度-出度 \(\ge 1\),蓝点则相反。
那么我们可以用上下界有源汇费用流解决,建图如下:
(Linux下画图真的很麻烦就直接用一下湘妹的吧
标签:红边,蓝边,Solution,网络,一拳,ge,link,打爆 From: https://www.cnblogs.com/Dark-Romance/p/16842588.html