#P6471. [thoi2012]社交网络结构洞
[thoi2012]社交网络结构洞
题目描述
给定一张 个顶点、 条边的无权无向图。记 为顶点 在原图中的最短距离,记 为删去顶点 及其关联边后, 的最短距离。
设 为 的邻居集合。顶点 的结构洞值为
$$\sum_{\substack{j,k\in N(i)\\j<k}}\bigl(d_i(j,k)-d(j,k)\bigr).$$每对不同的邻居只计一次。求每个顶点的结构洞值。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示一条连接 的无向边。顶点编号为 。
输出格式
输出 行,第 行一个整数,表示顶点 的结构洞值。
样例
5 7
2 4
5 4
3 2
3 4
3 1
5 3
5 1
0
0
1
0
0
删除顶点 后,顶点 和 的距离由 变成 ,其余被计入的邻居对距离不变。
数据范围
图中没有重边,删去任意一个顶点后其余顶点仍然连通。
| 测试点 | 上界 | 测试点 | 上界 | ||
|---|---|---|---|---|---|
| 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 |