「PA 2020」Skierowany graf acykliczny 题解

算法思路

本题使用二进制分解和分层构造的方法来构建有向无环图。核心思想是将目标路径数 $k$ 按二进制位分解，为每个二进制位构造对应的路径组件。

关键观察

1. 二进制表示

任意整数 $k$ 可以表示为：

$$k = \sum_{i=0}^u b_i \cdot 2^i \quad \text{其中 } b_i \in \{0,1\}, u = \lfloor \log_2 k \rfloor $$

2. 基本构造单元

对于每个二进制位 $i$，构造一个 $3$ 节点的模块：

节点n:     → 节点n+1
    ↘      ↗
    节点n+2

这个结构提供 $2$ 条路径（对应 $2^i$ 的系数）

代码解析

初始化与预处理

int k;
cin >> k;
vector<vector<int>> son(101);  // 存储每个节点的出边
int u = __lg(k);              // 计算k的二进制位数-1
int n = 1;                    // 当前节点编号
vector<int> pw(u + 1);        // 记录每个二进制位对应的关键节点

构造二进制位模块

for (int i = 0; i <= u; i++) {
    // 构造3节点模块
    son[n] = {n + 1, n + 2};    // 节点n有两条出边
    son[n + 1] = {n + 3};       // 节点n+1有一条出边  
    son[n + 2] = {n + 3};       // 节点n+2有一条出边
    pw[i] = n + 1;              // 记录关键节点
    n += 3;                     // 移动到下一组
}

连接目标节点

++n;  // 创建终点节点

for (int i = 0; i <= u; i++)
    if (k >> i & 1)             // 如果第i位为1
        son[pw[i]].push_back(n); // 从关键节点连接到终点

输出格式处理

for (int i = 1; i <= n; i++) {
    while (son[i].size() < 2)   // 确保每行输出两个数
        son[i].push_back(-1);   // 不足时用-1填充
    
    cout << son[i][0] << " " << son[i][1] << "\n";
}

构造示例

对于 $k = 3$（二进制 $11_2$）：

• $u = 1$（需要2个二进制位）
• 构造 $2$ 个模块（每个3节点）
• 总节点数：$1 + 2 \times 3 + 1 = 8$

图结构：

1 → 2 → 4 → 8
  ↘ 3 ↗

5 → 6 → 8
  ↘ 7 ↗

路径：$1→2→4→8$, $1→3→4→8$, $5→6→8$, $5→7→8$

算法正确性

路径计数原理

• 每个二进制位模块提供 $2$ 条路径
• 如果第 $i$ 位为 $1$，该模块的 $2^i$ 条路径被激活
• 总路径数 = $\sum_{b_i=1} 2^i = k$

约束条件满足

• 无环：所有边指向编号更大的节点
• 最多两条出边：每个节点出边数 ≤ $2$
• 无重边：同一节点的出边指向不同节点

复杂度分析

• 节点数量：$3 \cdot \lfloor \log_2 k \rfloor + 2 \leq 3 \cdot 30 + 2 = 92 < 100$
• 构造时间：$O(\log k)$
• 空间复杂度：$O(\log k)$

关键技巧

1. 二进制分解：将大数 $k$ 分解为 $2^i$ 的和
2. 模块化构造：为每个二进制位构造独立模块
3. 单调编号：确保所有边指向编号更大的节点，避免环
4. 格式适配：用 $-1$ 填充确保输出格式正确

该解法通过巧妙的二进制分解和模块化构造，成功解决了DAG路径计数的构造问题，是数学思维与图论构造的完美结合。