Description
Solution
容易发现各个位之间互不影响, 因此分开考虑每一位.
考虑题中是怎样的一个限制:
- 对每个点确定一个0/1的权值;
- 对于有连边且权值不同的点, 对答案有1的贡献;
- 求最小权值.
发现这就是对所有点的一个划分. 想到最小割. 其中从 (S) 集合连到 (T) 集合的边, 即为割边, 对答案的贡献为1. 其他边为0.
对于已有标号0的点, 连边 ((s,p,+infty)); 已有标号1的点, 连边 ((p,t,+infty));
对于原图中有的边 ((u, v)), 连边 ((u, v, 1)), ((v, u, 1)).
那么最小割即为这一位的答案.
考虑输出方案. 从前面的分析容易看出, 与 (s) 联通的点这一位权值为1, 其余点为0.
代码先咕了...