摆烂了，不想写代码了。
我怎么这么菜啊，看题解里说的各种思路，我一个都没想到。
哭
考虑给每个消息建一个点，每两个点之间连边 \(x \to y\)，边权为将 \(y\) 接在 \(x\) 后头能满足的条件数。
那么原问题就是找一条边权和最大的哈密顿路。
考虑特殊性质 C：那么就说明所有的边权不为 \(2\)，只有 \(\{0, 1\}\)。那么我们可以把它转化成最少路径覆盖的问题。
但是它不是 DAG，可能会有环。不过我们有一个性质：每个人都至少有一条学术消息。那么我们可以把环断开，然后把学术信息放开头 / 结尾，这样仍然能满足所有的条件。而新的这一堆消息的开头和结尾的人都一样，我们可以把它看做一整条学术消息。这样我们直接按照 DAG 跑最少链覆盖就是对的。
再优化下建图，就能 \(O(m \sqrt{m})\) 了。
然后考虑没有特殊性质 \(C\)：发现贪心的让这两个消息放在一块一定不劣。
所以可以让这两个先匹配在一起，剩下的跑最少链覆盖，构造方案的时候如果发现有环就断开然后插学术消息。
标签：省选,边权,消息,2022,联考,学术 From： https://www.cnblogs.com/apjifengc/p/17090312.html