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

7-12 社交网络图中结点的“重要性”计算(30 分)

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

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

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

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

输入格式:

输入第一行给出两个正整数N和M,其中N(≤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

输出样例:

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35
PTA 的数据之水我都没想到,可以说是非常之水了,floyd都能过了:
#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
int n,m;
const int maxn = 10010;
int maps[maxn][maxn];
int qus[maxn];
double ans[maxn];
void floyd()
{
    for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(maps[i][k]<inf && maps[k][j]<inf && maps[i][j]>maps[i][k]+maps[k][j])
                maps[i][j]=maps[i][k]+maps[k][j];
}
int calcu(int x)
{
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(x!=i) ans += maps[x][i];
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        maps[i][j] = inf;
    int a,b,k;
    while(m--){
        cin>>a>>b;
        maps[a][b] = 1;
        maps[b][a] = 1;
    }
    floyd();
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        printf("%d%c",maps[i][j],j==n?'\n':' ');
        */
    cin>>k;
    for(int i=1;i<=k;i++)
        cin>>qus[i];
    for(int i=1;i<=k;i++)
    {
        //printf("%d\n",calcu(qus[i]));
        printf("Cc(%d)=%.2lf\n",qus[i],(n-1)*1.0/(calcu(qus[i]*1.0)));
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3717 [AHOI2017初中组]cover

题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器,每个探测器有个探测半径r,问这n*n个点中有多少个点能被探测到。 输入输出...

2877
来自专栏专知

关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Array

点击上方“专知”,关注获取专业AI知识” 关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Ar...

32910
来自专栏Bingo的深度学习杂货店

Q221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square contai...

3335
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

3245
来自专栏恰同学骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

562
来自专栏灯塔大数据

每周学点大数据 | No.14 图论基础回顾

No.14期 图论基础回顾 Mr. 王:我们再讲一个时间亚线性算法——平面图直径的求解。平面图是图论中的一个概念,在大数据算法的很多地方都会涉及图的相关内容,...

3478
来自专栏趣学算法

切呀切披萨——最优三角剖分

有一块多边形的披萨,上面有各种各样的好吃的,我们希望沿着两个不相邻的两个顶点切成小三角形,尽可能少的切碎披萨上面的蔬菜、肉片。

811
来自专栏算法channel

回溯树求集合全排列和所有子集

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,深度搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学...

3209
来自专栏数据结构与算法

P2241 统计方形(数据加强版)

题目背景 1997年普及组第一题 题目描述 有一个n*m方格的棋盘,求其方格包含多少正方形、长方形 输入输出格式 输入格式: n,m因为原来数据太弱,现...

25911
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

3927

扫码关注云+社区