PTA数据结构与算法分析 36-7-36 社交网络图中结点的“重要性”计算 （30 分)_pta社交网络图中结点的“重要性”计算

7-36 社交网络图中结点的“重要性”计算 （30 分)在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有NNN个结点的网络中，结点viv_iv​i​​的“紧密度中心性”Cc(vi)Cc(v_i)Cc(v​i​​)数学上定义为viv_iv​i​​到其余所有结点vjv_jv​j​​ (j≠ij\ne ij≠i) 的最短距离d(vi,vj)d(v_i, v_j)d(v​i​​,v​j​​)的平均值的倒数：对于非连通图，所有结点的紧密度中心性都是0。给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。输入格式:输入第一行给出两个正整数NNN和MMM，其中NNN（≤104\le 10^4≤10​4​​）是图中结点个数，顺便假设结点从1到NNN编号；MMM（≤105\le 10^5≤10​5​​）是边的条数。随后的MMM行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数KKK（≤100\le 100≤100）以及KKK个结点编号，用空格分隔。输出格式:按照Cc(i)=x.xx的格式输出KKK个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后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
输出样例:Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35

思路：这是个求最短路径的问题，第一联想到的就是最短路径算法，而且这是个无权图，首先想到的就是《数据结构与算法分析》书中的无权最短路径的算法和dijkstra，我先尝试的是dijkstra(),一开始没想好，后来冷静想了一下，改进了下代码，然后AC了

代码如下：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0xffffff;
int N,M,K,flag = 0;
int d[10010][10010],dist[10010],vis[10010]
void initial(int st)
{
 memset(vis,0,sizeof(vis)); //执行dijkstra()算法前的初始化
 for(int i=1;i <= N;i++)
  dist[i] = inf;
 dist[st] = 0;
}
int findmin()//找到未知顶点中离起始点路径最短的点
{
 int minl = inf,mini = 0;
 for(int i=1;i <= N;i++){
  if(!vis[i] && dist[i] < minl){
   minl = dist[i];
   mini = i;
  }
 }
 return mini;
}
void dijkstra() 
{
 int S = findmin();
 if(!vis[S]){
  vis[S] = 1;
  for(int i=1;i <= N;i++){
   if(!vis[i]){
    if(dist[S] + d[S][i] < dist[i]){
     dist[i] = dist[S] + d[S][i];
    }
   }
  }
  dijkstra();
 }
}
/*void shortest(int st,int ed)  错误点  1
{
 queue<int> q;
 q.push(st);
 while(!q.empty()){
  int cur = q.front();q.pop();
  for(int i=1;i <= N;i++){
   if(dist[i] == inf && d[cur][i] < inf){
    dist[i] = dist[cur] + d[cur][i];
    q.push(i);
   }
  }
 }
}*/
void merge(int st)
{
 double center = 0;
 initial(st);
 dijkstra();
 if(!flag){
  for(int i=1;i <= N;i++){
  //initial()		错误点  2
  //dijkstra()   
  // shortest(st,i);
   center += dist[i];
  }
 }
 printf("Cc(%d)=%.2lf\n",st,flag?0:(N-1)/center);
}
int main()
{
 //freopen("D://in.txt","r",stdin);
 cin >> N >> M;
 for(int i=0;i < M;i++){
  int u,v;
  scanf("%d%d",&u,&v);
  d[u][v] = d[v][u] = 1;
  vis[u] = vis[v] = 1;
 }
 for(int i=1;i <= N;i++){
  for(int j=1;j <= N;j++)
   if(d[i][j] == 0)
    d[i][j] = d[j][i] = inf;
 }
 for(int i=1;i <= N && !flag;i++){ 
  if(!vis[i])
   flag = 1;//若有顶点不在任何一条边上，则不连通
 }
 cin >> K;
 for(int i=0;i < K;i++){
  int temp;
  scanf("%d",&temp);
  merge(temp);//求最短路径算法的驱动例程
 }
// fclose(stdin);
 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

错误点1： shortest是尝试用无权最短路径算法求解，
不过我没写好，只能过前三个测试点，最后一个会超时

错误点2：错误点2的initial()与dijkstra()算法一开始我是放在
for循环里面的，认为既然要求两个点之间的最短路径就要重复调用，但后来仔细一想，dijkstra()算法是求出从起始点到其他所有点之间的最短路径，根本不用重复调用，把它调到外面后AC了。