问题分析

我们需要将 $M$ 条消息重新排列，使得尽可能多的「楼上型消息」和「楼下型消息」符合实际情况。

核心规则回顾：

• 楼下型消息：要求上一条消息的发送者 = 本消息提到的网友
• 楼上型消息：要求下一条消息的发送者 = 本消息提到的网友
• 学术消息：永远不符合实际情况，但每个人至少有一条

---

关键观察

1. 图论建模

将每个网友看作图中的一个节点。

对于消息建立两种类型的有向边：

• 楼下型边：从「发送者」指向「提到的网友」，表示如果这条消息是楼下型，那么它的前一条消息应该由提到的网友发送
• 楼上型边：从「提到的网友」指向「发送者」，表示如果这条消息是楼上型，那么它的后一条消息应该由提到的网友发送

2. 问题转化

在排列中，每条符合实际情况的楼上型/楼下型消息对应图中一条被「实现」的边。

更具体地：

• 如果边 $u \to v$ 是楼下型边且被实现，意味着在排列中存在连续两条消息 $(x, u \to v)$，其中 $x$ 的发送者是 $u$
• 如果边 $u \to v$ 是楼上型边且被实现，意味着在排列中存在连续两条消息 $(u \to v, x)$，其中 $x$ 的发送者是 $v$

这实际上是一个路径覆盖问题：我们要用若干条路径覆盖图中的一些边，使得覆盖的边数最多。

---

核心解法

1. 网络流模型

建立网络流模型：

• 源点 $S$，汇点 $T$
• 对每个网友 $u$，拆成两个点 $u_{in}$ 和 $u_{out}$
• $S \to u_{in}$：容量 = $u$ 的入度（或适当的值）
• $u_{out} \to T$：容量 = $u$ 的出度（或适当的值）
• 对于每条楼下型边 $u \to v$：从 $u_{out}$ 到 $v_{in}$ 连容量为 1 的边
• 对于每条楼上型边 $u \to v$：从 $u_{out}$ 到 $v_{in}$ 连容量为 1 的边

最大流的值就是最大能实现的符合实际情况的消息数量。

2. 构造排列方案

通过网络流的流量分配，我们知道哪些边被选中。

然后需要构造具体的排列：

1. 找出流路径：根据网络流结果，找出若干条从 $S$ 到 $T$ 的路径
2. 路径对应消息序列：每条路径对应排列中的一个连续段
3. 插入学术消息：在路径之间、路径内部适当位置插入学术消息，确保：
   • 每个人至少有一条学术消息
   • 不破坏已实现的楼上型/楼下型关系

3. 特殊性质的处理

• 性质 A（无楼上型消息）：问题简化为只考虑楼下型消息，可以用更简单的方法
• 性质 B（存在完美排列）：网络流能实现所有边上限
• 性质 C（无双向边）：简化了图的结构，避免循环依赖

---

算法步骤

1. 建图与网络流

• 构建上述网络流模型
• 跑最大流算法（Dinic 等）
• 记录流量分配

2. 路径提取

• 从网络流结果中提取若干条路径
• 每条路径对应一个消息链：
  • 路径 $u_1 \to u_2 \to \cdots \to u_k$ 对应消息序列：
    • 楼下型边 $u_1 \to u_2$
    • 楼下型边 $u_2 \to u_3$
    • ...
    • 最后一条边如果是楼上型，需要特殊处理

3. 排列构造

• 将各个路径连接起来形成主干
• 在适当位置插入学术消息：
  • 确保每个人至少一条学术消息
  • 不破坏已实现的楼上型/楼下型关系
• 剩余未使用的消息随意放置

---

复杂度分析

• 网络流：$O(M^{1.5})$ 或 $O(M^2)$，对于 $M \le 77,777$ 可接受
• 路径提取：$O(M)$
• 构造排列：$O(M)$

由于 $\sum M \le 2.5 \times 10^5$，总复杂度可接受。

---

难点与技巧

1. 楼上型与楼下型的统一处理

楼上型和楼下型在图中方向相反，但在网络流模型中可以用相同方式处理。

2. 学术消息的插入

学术消息虽然不贡献答案，但：

• 必须保证每个人至少一条
• 插入时不能破坏已实现的楼上型/楼下型关系
• 可以作为路径之间的「缓冲」

3. 具体排列的构造

从网络流结果到具体排列需要仔细设计：

• 路径的连接顺序
• 学术消息的放置位置
• 边界情况的处理

---

总结

这道题的核心在于：

1. 图论建模：将消息抽象为有向边
2. 网络流算法：计算最大可实现的消息数量
3. 构造算法：从网络流结果构造具体排列
4. 细节处理：学术消息的插入和边界情况

通过将排列问题转化为图论中的路径覆盖问题，再利用网络流求解最大值，最后精心构造排列方案，体现了「建模 → 求解 → 构造」的经典解题思路。