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 条评论
登录 后参与评论

相关文章

来自专栏Duncan's Blog

ccx

641
来自专栏木东居士的专栏

漫谈机器学习之小知识点总结

1654
来自专栏PPV课数据科学社区

机器学习几个基本的问题

关键词:机器学习、推荐系统、文本挖掘 正文如下: 从今年四月份到现在已经工作快9个月了,最开始是做推荐系统,然后做机器学习,现在是文本挖掘,每个部分研究的时间...

3227
来自专栏数据科学学习手札

(数据科学学习手札21)sklearn.datasets常用功能详解

作为Python中经典的机器学习模块,sklearn围绕着机器学习提供了很多可直接调用的机器学习算法以及很多经典的数据集,本文就对sklearn中专门用来得到已...

3459
来自专栏深度学习入门与实践

【深度学习】用PaddlePaddle进行车牌识别(二)

  上节我们讲了第一部分,如何用生成简易的车牌,这节课中我们会用PaddlePaddle来识别生成的车牌。 ---- 数据读取   在上一节生成车牌时,我们可...

4728
来自专栏奇点大数据

Pytorch神器(11)

看上去这么乱乱的图就是目标检测应用的输出了,简单说,目标检测的任务就是输入一张图片或者一帧图像,通过一系列计算,使得输出是这样的一个可视化结果或一个等同于这种可...

1443
来自专栏人工智能头条

美团网内部分享:机器学习中的数据清洗与特征处理实践

2023
来自专栏人工智能头条

AI从入门到放弃2:CNN的导火索,用MLP做图像分类识别?

1082
来自专栏技术随笔

[译] Instance Normalization: The Missing Ingredient for Fast Stylization

3518
来自专栏人工智能

6种机器学习算法要点

本文旨在为人们提供一些机器学习算法,这些算法的目标是获取关于重要机器学习概念的知识,同时使用免费提供的材料和资源。当然选择有很多,但哪一个是最好的?哪两个互相补...

2079

扫码关注云+社区