题解思路

1. 建模与符号

   • 设节点数为 $N$，边集为 edges，每条边 $(u, v)$ 表示从 $u \to v$。

   • 构造列随机转移矩阵 $S\in \mathbb{R}^{N\times N}$，令第 $j$ 列表示“从节点 $j$”在一步内跳到各节点的概率分布：

     $$S_{ij}=\Pr(j\to i)$$

     因此每一列和为 1。

2. 处理悬挂节点（无出边）

   • 若节点 $j$ 出度为 0，则按题意把其出边分布设为均匀分布：第 $j$ 列全为 $1/N$。

3. 普通节点的列向量

   • 若节点 $j$ 出度为 $\text{outdeg}(j)>0$，则对其每条出边 $j\to i$ 计入 $S_{ij} += 1/\text{outdeg}(j)$。 （若输入里有重复边，出度与计数一致，列和仍为 1。）

4. 幂迭代（列随机形式）

   • 设阻尼系数 $d=0.85$，随机跳转向量 $v=\frac{1}{N}\mathbf{1}$，初始 $r^{(0)}=v$。

   • 迭代更新：

     $$r^{(t+1)}=d\,S\,r^{(t)}+(1-d)\,v$$

   • 以 $L_1$ 范数做收敛判据：$\|r^{(t+1)}-r^{(t)}\|_1<10^{-8}$ 时停止；否则最多迭代 1000 次。

   • 在固定 $d$ 下，该过程收敛到唯一平稳分布（无需平局处理）。

5. 输出

   • 将最终 $r$ 按节点编号从小到大输出为JSON 数组，并对每个分量执行 round(x, 6)。

python

import sys
import json
import re
import numpy as np

def _sanitize_json_like(s: str) -> str:
    """把常见“看起来像 JSON 但不合法”的输入修正为合法 JSON。
    - 去掉 BOM
    - 去掉 // 和 /* */ 注释
    - 替换中文引号为 ASCII 引号
    - 替换中文标点（：，；）为对应英文；并把 key 后面的分号修正为冒号
    - 去掉结尾多余逗号
    - 把 `] ; "key"` 这种把分号当分隔符的情况修成逗号
    对于本就合法的 JSON，这些替换是“无害”的（基本为 no-op）。
    """
    s = s.lstrip("\ufeff").strip()

    # 去注释
    s = re.sub(r'//.*?(?=\n|$)', '', s)             # 行注释 //
    s = re.sub(r'/\*.*?\*/', '', s, flags=re.S)     # 块注释 /* */

    # 统一引号为 ASCII 双引号
    s = (s.replace('“', '"').replace('”', '"')
           .replace('„', '"').replace('‟', '"').replace('＂', '"'))

    # 中文标点转英文
    s = s.replace('：', ':').replace('，', ',').replace('；', ';')

    # 修正：键名后误用了分号（如 "N";2）→ 冒号
    s = re.sub(r'("[-\w]+")\s*;\s*', r'\1: ', s)

    # 某些人用分号分隔项： ] ; "key" → ], "key"
    s = re.sub(r'\]\s*;\s*(")', r'], \1', s)

    # 去掉对象/数组末尾多余逗号：{... ,} 或 [... ,]
    s = re.sub(r',\s*([}\]])', r'\1', s)

    return s

def main():
    # 读取整段输入并清洗
    raw = sys.stdin.read()
    cleaned = _sanitize_json_like(raw)

    # 尝试解析
    try:
        data = json.loads(cleaned)
    except json.JSONDecodeError as e:
        # 解析仍失败时，给出更直观的提示并打印原始与清洗后的前后文
        msg = (
            "输入不是合法 JSON（请确保用英文冒号/逗号/引号且无注释）。\n"
            f"JSONDecodeError: {e}\n"
            "示例合法输入：{\"edges\":[[0,1],[1,0]],\"N\":2}\n"
        )
        print(msg, file=sys.stderr)
        raise

    edges = data.get("edges", [])
    N = int(data["N"])

    # 超参数
    d = 0.85
    max_iter = 1000
    tol = 1e-8

    # 构造列随机矩阵 S，S[i, j] = P(j -> i)
    S = np.zeros((N, N), dtype=float)

    # 统计出度
    outdeg = np.zeros(N, dtype=int)
    for u, v in edges:
        if 0 <= u < N and 0 <= v < N:
            outdeg[u] += 1

    # 悬挂节点：整列置为 1/N
    for j in range(N):
        if outdeg[j] == 0:
            S[:, j] = 1.0 / N

    # 非悬挂节点：按出度均分
    for u, v in edges:
        if 0 <= u < N and 0 <= v < N and outdeg[u] > 0:
            S[v, u] += 1.0 / outdeg[u]

    # 幂迭代
    r = np.full(N, 1.0 / N, dtype=float)  # 初始均匀分布
    teleport = (1.0 - d) / N

    for _ in range(max_iter):
        r_new = d * (S @ r) + teleport
        if np.abs(r_new - r).sum() < tol:
            r = r_new
            break
        r = r_new

    # 归一，防微小数值误差
    ssum = r.sum()
    if ssum > 0:
        r = r / ssum

    # 输出：按要求 round 到 6 位并以 JSON 数组打印
    out = [round(float(x), 6) for x in r.tolist()]
    print(json.dumps(out, ensure_ascii=False))

if __name__ == "__main__":
    main()

题目内容

请手写实现经典 $PageRank$ 算法(列随机、幂迭代形式)，用于极小的有向图(节点 $≤6$ 个)。

1.固定超参数

阻尼系数 $d$ $0.85$

随机跳转 $(1-d)/N$

收敛判据 当两次迭代 $L1$ 差 $<1e-8$ 或迭代次数达 $1000$ 即停止

初始 $PageRank$ 向量为均匀分布 $(1/N,...,1/N)$ 。

2.输出格式

一行：长度为 $N$ 的 $JSON$ 数组，依节点编号顺序给出最终 $PageRank$ 。

3.确定性说明

幂迭代在固定阻尼系数下会收敛到唯一的平稳分布；无需额外平局处理。

输入描述

一行 $JSON$ ：

{
 "edges”:[[u1,v1],[u2,v2],…]，//有向边，节点编号从0开始"
 "N”:4                   / 节点总数(2≤N≤6)
}

若某节点没有任何出边(悬挂节点)，请在构造转移矩阵时对出边(悬挂节点)做均匀分布处理。

输出描述

使用 $round(x,6)$ 保留小数位即可

示例：

$[0.486486,0.256757,0.256757]$

补充说明

为了确保通过测试用例，仅使用 $NumPy$ 实现

样例1

输入

{"edges":[[0,1],[1,0]],"N";2}

输出

[0.5,0.5]