#P6471. [thoi2012]社交网络结构洞

    ID: 5065 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高广度优先搜索零贡献剪枝离线查询

[thoi2012]社交网络结构洞

题目描述

给定一张 nn 个顶点、mm 条边的无权无向图。记 d(j,k)d(j,k) 为顶点 j,kj,k 在原图中的最短距离,记 di(j,k)d_i(j,k) 为删去顶点 ii 及其关联边后,j,kj,k 的最短距离。

设 N(i)N(i) 为 ii 的邻居集合。顶点 ii 的结构洞值为

$$\sum_{\substack{j,k\in N(i)\\j<k}}\bigl(d_i(j,k)-d(j,k)\bigr).$$

每对不同的邻居只计一次。求每个顶点的结构洞值。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行两个整数 ai,bia_i,b_i,表示一条连接 ai,bia_i,b_i 的无向边。顶点编号为 1,…,n1,\ldots,n。

输出格式

输出 nn 行,第 ii 行一个整数,表示顶点 ii 的结构洞值。

样例

5 7
2 4
5 4
3 2
3 4
3 1
5 3
5 1
0
0
1
0
0

删除顶点 33 后,顶点 11 和 22 的距离由 22 变成 33,其余被计入的邻居对距离不变。

数据范围

图中没有重边,删去任意一个顶点后其余顶点仍然连通。

测试点 nn mm 上界 测试点 nn mm 上界
1 5 10 11 800 30000
2 10 50 12 900 40000
3 50 300 13 1000 10000
4 200 1000 14 50000
5 2000 15 1500 20000
6 300 3000 16
7 400 8000 17 1800 15000
8 500 10000 18 1900 10000
9 600 12000 19 2000 6000
10 700 5000 20 10000

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页