联合省选 2022 学术社区 Analysis

· · 题解

特殊性质 B 部分分

观察到输出的合法信息数正确就可以得到 50% 的分数，而特殊性质 B 存在某个方案每条非学术消息都合法，故直接计算输入中的楼上型消息与楼下型消息的数量和即可，获得 20 分。

测试点 1

爆搜，获得 4 分。

测试点 2

状压 DP，获得 8 分。

特殊性质 ABC

注意到一条消息连接两个人并且有明显的指向关系，可以想到使用图论建模描述方案。对于每个人建立一个点，对于每条消息 A B louxia 从 B 向 A 连一条边（这是因为它之后的消息指向的是 A 不是 B），对于一条学术消息放在其发出者对应的节点上。观察合法方案，其应该由若干条链构成，每一条链从一个点的学术消息开始，在图上走一段路径，最后可以在任意一个点结束。也就是说，我们需要把图上的所有边进行覆盖。

图论中讨论到边覆盖的算法模型是欧拉回路，当然为了让链覆盖变成欧拉回路需要一些小小的技巧：建立一个虚点 T，对于一个 A 发出的学术消息从 T 向 A 连一条边。对于每个非虚点，若其入度减出度为 d，则从它往 T 连 d 条边。首先这个 d 一定不会是负数，否则必然存在一条从它发出的边对应的消息不符合实际情况。对新图从 T 开始跑欧拉回路得到的方案去掉所有没用的边就得到了一个合法的方案。当然还有一个问题是为啥这个图一定联通，这是因为每个人都会发一条学术消息。

该算法可以通过 7 个测试点，加上以上所有的部分分，共可以获得 42 分。

特殊性质 AC

沿用 ABC 的算法，问题在于有一些点由于入度小于出度，对于额外的（出度减去入度）条消息是一定无法满足实际情况的，由此我们可以计算出答案的一个下界。同时我们可以简单地构造一个方案使得答案恰好为这个下界：对于每个出度大于入度的点，从 T 向它连若干条边使其入出度平衡，然后跑一遍欧拉回路。对于这样加入的每一条边，它在欧拉回路中连接的下一条边对应的消息不满足实际情况，而其他消息都满足实际情况。

该算法可以额外通过 3 个测试点，加上以前所有的部分分，共可以获得 54 分。

特殊性质 BC

再一次观察最终的方案。其仍然可以划分成若干条链，因为满足特殊性质 C，所以每条链一定是若干条楼上消息+中间的一条学术消息+若干条楼下消息（若干可以是零）。这引导我们建立分层图描述方案。具体地，建立二层图 G_1,G_2，每个人在 G_1,G_2 中都对应一个点。对于一条楼上型消息 A B loushang，在 G_1 中从 A 向 B 连一条边；对于一条学术消息，从 G_1 对应节点向 G_2 对应节点连一条边；对于一条楼下型消息 A B louxia，在 G_2 中从 B 向 A 连一条边。那么一条方案中的链对应的就是从 G_1 的任意一个点开始到 G_2 的任意一个点结束的一条路径，我们需要找到一个路径对边的覆盖。

仍然沿用特殊性质 ABC 的做法：建立一个虚点 T，对于每个 G_1 中的点，通过 T 向它连边使其入出度平衡，对于每个 G_2 中的点，通过从它向 T 连边使其入出度平衡，然后运行欧拉回路算法得到一个方案。

该算法可以额外通过 5 个测试点，加上以前所有的部分分，共可以获得 64 分。

特殊性质 C

继续沿着之前的思路走，现在不一定每条边都出现在方案里了，我们要如何选择舍弃的边呢？

之前的所有算法都在平衡图上每个点的点度以保证欧拉回路的存在，那么继续沿着这个想法行进。对于 G_1 中的点，入度大于出度时，会有（入度减出度）那么多条边无法匹配；而 G_2 中则是入出度反过来。那么与特殊性质 AC 类似，我们首先有了一个答案的下界。但是没有优化空间了吗？

仔细想想舍弃一条边意味着什么。对于一条 A B loushang，如果我们舍弃它，其实意味着这条消息被我们认作了功能与学术消息等同的消息，也就是说，原本是 G_1 中 A 连向 B，现在是 G_1 中的 A 连向 G_2 中的 A，此时 G_1 中的 B 入度减少 1，G_2 中的 A 入度增加 1，对于两个点来说条件都松弛了 1！也就是说，如果这两个点在开始的时候都需要舍弃边，那么通过舍弃 A B loushang 这条边，下界可以往上加 1。

这样看来，我们希望尽可能多的找到这样的边，那么下界就可以抬升得尽可能大，而这个最大值很显然对应着答案。找这样的边的过程可以使用二分图网络流模型刻画：对于每个 G_1 中的点 A_1，如果其出度 d_{out}(A_1) 小于入度 d_{in}(A_1)，从 S 向 A_1 连流量为 -d_{out}(A_1) + d_{in}(A_1) 的边；对于每个 G_2 中的点 A_2，如果其入度小于出度，从 A_2 向 T 连流量为 d_{out}(A_2) - d_{in}(A_2) 的边；对于一条 A B loushang 消息，从 B_1 向 A_2 连一条流量为 1 的边；对于一条 A B louxia 消息，从 A_1 向 B_2 连一条流量为 1 的边。对建立的网络流图跑最大流，最大流量就对应着下界的最大抬升量，而对应的方案就是舍弃了之后能让下界增加 1 的边集。

将这些边舍弃（这指的是将它们变成对应的学术边）之后，再运行 BC 和 AC 思想结合的算法得到欧拉回路即可找到对应方案。

该算法可以额外通过 5 个测试点，结合之前的所有算法可获得 80 分。

最终算法

最后一个问题是需要解决特殊性质 C 中提到的对边。其发生的变化是：链的中间不一定由一条学术消息作为中转，而是用一对 A B loushang 和 B A louxia。我们容易对方案进行调整或者对网络流得到的最终方案进行分析，得到将这样的一对消息放在一起总是不劣的，所以将它们拼在一起之后，就变成了 A_1 \to B_2 的一条边，这样的边在特殊性质 C 的网络流中不需要进行任何决策，所以将这样的边缩起来之后更新度数运行特殊性质 C 算法即可。

该算法可以通过最后 5 个测试点，获得满分。

Bonus

如果去掉题目中的每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息这题能不能做呢？

去掉这个条件的难点在于，G_1 和 G_2 中可能存在入出度平衡的连通块，对于它们需要额外用一条边让虚点 T 与它们联通。而在网络流决策的过程中，可能会出现一个 G_1 中导出子图入出度平衡的、不向子图外连边的 SCC 由于 G_1 中其他点连向它们的边都被网络流舍弃光了导致这个连通块需要额外的 1 的代价。而这个代价作为 SCC 一个整体出现，又与特殊性质 C 中的单点代价有所不同，它们很难整合在同一个网络流模型中。

如果大家有什么想法可以与我讨论。