【PAT数据结构与算法题目集】社交网络图中结点的“重要性”计算（单源最短路径）_66hhkk

【PAT数据结构与算法题目集】社交网络图中结点的“重要性”计算（单源最短路径）

题目

在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。

“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中，结点 $v{}_i$ 的“紧密度中心性” $Cc(v_{}i)$ 数学上定义为 $v_i$ 到其余所有结点 $v_j(j̸=i)$ 的最短距离 $d(v_{}i,v_{}j)$ 的平均值的倒数：

对于非连通图，所有结点的紧密度中心性都是0。
给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。

输入格式:
输入第一行给出两个正整数N和M，其中$N(\le 10^4)$是图中结点个数，顺便假设结点从1到N编号；M（≤10^​5）是边的条数。随后的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K（≤100）以及K个结点编号，用空格分隔。

输出格式:
按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。

输入样例:

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出样例:

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35
1
2
3

思路

这道题题目看似复杂，实际上是一道很简单的单源最短路径问题。

代码

#include <iostream>
#include <stdio.h>
#include <string>
#include<string.h>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

#define MAXIMUM 10020

typedef struct node {
    int data;
    double fre;
};

int graph[10005][10005];
int dis[10005];
int tip[10005];
node nodes[105];

int main() {

    int n, m, k, i, j, a, b, ans, kk;
    queue<int>q;
    while(~scanf("%d%d", &n, &m)) {
        for(i=1; i<=n; i++) {
            for(j=i+1; j<=n; j++) {
                graph[i][j] = graph[j][i] = MAXIMUM;
            }
        }
        for(i=0; i<m; i++) {
            scanf("%d%d", &a, &b);
            graph[a][b] = graph[b][a] = 1;
        }

        scanf("%d", &k);
        for(kk=0; kk<k; kk++) {
            scanf("%d", &a);
            memset(tip, 0, sizeof(tip));
            for(i=1; i<=n; i++) {
                if(i == a) {
                    dis[i] = 0;
                }
                else {
                    dis[i] = MAXIMUM;
                }
            }

            while(!q.empty()) {
                q.pop();
            }
            q.push(a);
            ans = 0;

            //cout<<"hehe"<<endl;

            while(!q.empty()) {
                b = q.front();
                q.pop();
                if(tip[b]) {
                    continue;
                }
                tip[b] = 1;
                ans++;

                for(i=1; i<=n; i++) {
                    if(tip[i]==0 && dis[i] > dis[b] + graph[b][i] ) {
                        dis[i] = dis[b] + graph[b][i];
                        q.push(i);
                    }
                }
            }

            if(ans < n-1) {
                nodes[kk].data = a;
                nodes[kk].fre = 0;
            }
            else {
                nodes[kk].data = a;
                b = 0;
                for(i=1; i<=n; i++) {
                    if(i != a) {
                        b = b + dis[i];
                    }
                }
                nodes[kk].fre = (double)(n-1) / (double)b;
            }

        }


        for(i=0; i<k; i++) {
            printf("Cc(%d)=%.2f\n",nodes[i].data,nodes[i].fre);
        }


    }

    return 0;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104