PTA 社交网络图中结点的“重要性”计算

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

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

对于非连通图，所有结点的紧密度中心性都是0。

给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。

输入格式:

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

输出样例:

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

解题思路：最短路

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int dis[10005]; int s[200005],nt[200005],e[200005]; int visit[10005]; int n,m; int k,ss; struct node { int id; int sum; friend bool operator <(node p,node q) { return p.sum>q.sum; } }pre,nt1; void Dijkstra(int x) { for(int i=1;i<=n;i++) visit[i]=0,dis[i]=INF; dis[x]=0; pre.id=x,pre.sum=0; priority_queue<node>q; q.push(pre); while(!q.empty()) { pre=q.top(); q.pop(); int id=pre.id; visit[id]=1; for(int i=s[id];~i;i=nt[i]) { int ee=e[i]; if(visit[ee]) continue; if(dis[ee]>dis[id]+1) { dis[ee]=dis[id]+1; nt1.id=ee; nt1.sum=dis[ee]; q.push(nt1); } } } } int main() { while(~scanf("%d %d",&n,&m)) { int f,t,cnt=1; memset(s,-1,sizeof s); memset(nt,-1,sizeof nt); for(int i=1;i<=m;i++) { scanf("%d %d",&f,&t); nt[cnt]=s[f],s[f]=cnt,e[cnt++]=t; nt[cnt]=s[t],s[t]=cnt,e[cnt++]=f; } scanf("%d",&k); while(k--) { scanf("%d",&ss); Dijkstra(ss); double sum=0; for(int i=1;i<=n;i++) if(i!=ss) sum+=dis[i]; printf("Cc(%d)=%.2lf\n",ss,(n-1)/sum); } } return 0; }