测测你的网页排序-scale20 排行榜


时间限制: 15 s
空间限制: 2097152 KB

题目描述

给定一个有 n 个顶点、m 条边的有向图,计算所有顶点的 PageRank 值。阻尼系数 d = 0.85,传送到每个顶点的概率相同;没有出边的顶点将其质量均匀分配给全部顶点。结果按所有顶点的平均值为 1 归一化。

顶点编号为 0 到 n-1,自环和重复边均保留,重复边计入出度的重数。答案是下面方程的唯一解,不以固定迭代轮数定义。记 degree[u] 为顶点 u 的出度,r[v] 为答案:

$$ r[v]=1-d+\frac{d}{n}\sum{u:\,degree[u]=0}r[u] +d\sum{(u,v)\in E}\frac{r[u]}{degree[u]},\qquad \sum_{v=0}^{n-1}r[v]=n. $$

接口

```cpp struct Edge { unsigned src, dst; };

void pagerank(unsigned n, unsigned m, const Edge *A, double *rank); ```

A 为长度 m 的 COO 边数组,A[i] 表示一条从 A[i].src 到 A[i].dst 的有向边,不附带边权。将第 i 个顶点的答案写入 rank[i]。

A 和 rank 的起始地址均为 4096 字节对齐;A 只读,rank 初值均为 0,仅用于输出。输出类型为 double。

判定方式

标准参考答案相对于上述方程真实解的相对或绝对误差保证不超过 1e-9。

你的答案被认为是正确的,当且仅当所有输出均为有限数,并且每个顶点的相对或绝对误差不超过 1e-6,即

text abs(rank[i] - reference[i]) <= 1e-6 * max(1, abs(reference[i]))

随机数据生成

稀疏结构采用下面明确约定的有向 Graph500 Kronecker 生成算法。只对随机种子保密;算法、常量、生成顺序均公开。每个测试点使用固定种子。

记 scale = log2(n),所有顶点编号从 0 到 n-1,依次生成编号为 k = 0, 1, ..., m-1 的边。不进行 clip-and-flip,不补反向边,不删除自环或重复边,也不另外打乱边的顺序。

MRG 随机数发生器

状态为五元组 (z1,z2,z3,z4,z5),模数 M=2147483647。初始五元组是保密种子,各分量属于 [1,M-1]。一次取数执行:

text t = (107374182*z1 + 104480*z5) mod M (z1,z2,z3,z4,z5) = (t,z1,z2,z3,z4) return t

用 T 表示一次状态转移,T^q(S) 表示从状态 S 连续执行 q 次转移后的状态;实际生成器用矩阵快速幂计算跳跃,与连续执行的定义完全相同。

每条边的未重编号端点

设初始状态为 S。第 k 条边从独立跳跃状态 T^(k*2^64)(S) 开始取数,初始 a=b=0。重复以下过程 scale 次:

  1. 从该状态取数 r;若 r<3647,重新取数,直到 r>=3647。
  2. 令 q=r mod 10000,按下表取位 (u,v)。
  3. 执行 a=2*a+u、b=2*b+v。

| q 的范围 | (u,v) | 概率 | | --- | --- | --- | | 0 <= q < 1900 | (0,1) | 0.19 | | 1900 <= q < 3800 | (1,0) | 0.19 | | 3800 <= q < 9500 | (0,0) | 0.57 | | 9500 <= q < 10000 | (1,1) | 0.05 |

各层使用相同的概率,不引入额外噪声。

顶点重编号

另从状态 T^(50*2^128+7*2^64)(S) 连续取四个数 r0,r1,r2,r3,定义

text val0 = r0*(2^32-1)+r1 val1 = r2*(2^32-1)+r3

对 a、b 分别调用同一个 scramble,结果作为 src、dst。以下伪代码的变量均为64位无符号整数,加法、乘法按模 2^64 计算;reverse64 反转全部64个二进制位,| 为按位或。

cpp uint64_t scramble(uint64_t v) { v += val0 + val1; v *= val0 | 0x4519840211493211ULL; v = reverse64(v) >> (64 - scale); v *= val1 | 0x3050852102C843A5ULL; v = reverse64(v) >> (64 - scale); return v; }

数据范围

n 等于 1,048,576(2^20),m 等于 16,777,216(2^24)。

题目来源

saffah_codex_maker


关于接口中的数组初值说明(最后更新:2023年2月6日)

若题目要求实现函数接口,且该函数中存在仅用于输出的数组(如 void solve(int n, const int *in, int *out) 中的 out),那么除非另外说明,否则该数组在程序启动时的初值为 0。

关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。

关于提交的说明

你提交的代码将会被公开,所有人都可见。如果这不是你所期望的,或者如果想要删除已提交的代码,请联系管理员。




Judge Duck Online | 评测鸭在线
Server Time: 2026-11-18 09:37:14 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠