题意就不说了,其他题解写的都很好。
分析
明明这题第一个 tag 就是网络瘤流,却没有一篇网络流的题解 qwq。
首先是染色,确定每对曾经跳过舞的学生的性别。
第一个坑,数据不保证无环,所以要这么写:
1 | void color(int x, int c) { |
有人或许不理解怎么出现环,这里给出一组数据:
1 | 5 4 |
第二个坑,数据不保证每组前面一定是同种性别。于是你直接建模会收获 40 pts 的好成绩。
我的做法可能有点复杂,供参考。
1 | auto* c = new Color(); // 完整代码最后会放在云剪贴板里 |
最后注意数据并不保证图的联通,染色的时候不能只跑一遍。
建模
众所周知,网络流主要考建模。
这道题的建模不算很复杂,具体的分析可以看其他题解。
求最大独立集不好求,所以我们求最大匹配,转换为网络流上的最大流。输出答案的时候再拿总点数减一下就好了。
- 不妨假设 \(u\) 的性别为 \(0\), \(v\) 的性别为 \(1\)。
- 建立容量为 \(1\) 的一条边 \((u,v)\) 。
- 建立超级源点 \(S'\) ,超级汇点 \(T'\)。
- 对于每一个 \(u\) 建立容量为 \(1\) 的一条边 \((S',u)\)。
- 对于每一个 \(v\) 建立容量为 \(1\) 的一条边 \((v,T')\)。
就好了啊 qwq。最后流向 \(t\) 的最大流就是二分图上的最大匹配。
还是不太理解的话可以看一下图:
最后附上完整代码