BZOJ1491 - [NOI2007]社交网络

2017/02/13

题目

在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象。
不妨看这样的一个问题。在一个社交圈子里有n 个人,人与人之间有不同程 度的关系。我们将这个关系网络对应到一个n 个结点的无向图上,两个不同的人 若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值c, c 越小,表示两个人之间的关系越密切。
我们可以用对应结点之间的最短路长度来衡量两个人 s 和t 之间的关系密切 程度,注意到最短路径上的其他结点为s 和t 的联系提供了某种便利,即这些结 点对于s 和t 之间的联系有一定的重要程度。我们可以通过统计经过一个结点v 的最短路径的数目来衡量该结点在社交网络中的重要程度。
考虑到两个结点 A 和B 之间可能会有多条最短路径。我们修改重要程度的定 义如下:
令 Cs,t 表示从s 到t 的不同的最短路的数目,Cs,t(v)表示经过v 从s 到t 的最短 路的数目;则定义

为结点 v 在社交网络中的重要程度。
为了使 I(v)和Cs,t(v)有意义,我们规定需要处理的社交网络都是连通的无向 图,即任意两个结点之间都有一条有限长度的最短路径。
现在给出这样一幅描述社交网络的加权无向图,请你求出每一个结点的重要 程度。

跑一遍 Floyd ,一边跑一边统计最短路径的条数。

判断 的最短路径经过 v :

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <limits>
using namespace std;
typedef long long LL;
const int MAX_N = 110;
const LL LLINF = 1E18L;
LL G[MAX_N][MAX_N];
LL S[MAX_N][MAX_N];

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            G[i][j] = i == j ? 0 : LLINF;
            S[i][j] = 1;
        }
    }

    int u, v, c;
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &u, &v, &c);
        G[u][v] = G[v][u] = c;
        S[u][v] = S[v][u] = 1;
    }

    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) {
                if(i == k || k == j || i == j) continue;
                if(G[i][k] + G[k][j] < G[i][j]) {
                    G[i][j] = G[i][k] + G[k][j];
                    S[i][j] = S[i][k] * S[k][j];
                } else if(G[i][k] + G[k][j] == G[i][j])
                    S[i][j] += S[i][k] * S[k][j];
            }

    double ans = 0.0;
    for(int k=1;k<=N;k++) {
        ans = 0.0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(i != j && i != k && j != k && G[i][k] + G[k][j] == G[i][j])
                    ans += 1.0 * S[i][k] * S[k][j] / S[i][j];
        printf("%.3lf\n", ans);
    }
}