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

相关文章

来自专栏程飞翔的专栏

XGBoost 源码阅读笔记(2):树构造之 Exact Greedy Algorithm

本篇将继续向大家介绍 XGBoost 源码是如何构造一颗回归树,不过在分析源码之前,还是有必要先和大家一起推导下 XGBoost 的目标函数。

8691
来自专栏专知

【论文推荐】最新八篇情感分析相关论文—注意力网络、多模态情感分析、情感分析局限性、跨语言情感分类、多语言情感分析

【导读】专知内容组今天推出最新八篇情感分析(Sentiment Analysis)相关论文,欢迎查看!

4282
来自专栏小鹏的专栏

tf25: 使用深度学习做阅读理解+完形填空

记的在学生时代,英语考试有这么一种类型的题,叫:阅读理解。首先让你读一段洋文材料,然后回答一些基于这个洋文材料提的问题。 我先给你出一道阅读理解 Big ...

5295
来自专栏AI研习社

手把手教你用 Keras 实现 LSTM 预测英语单词发音

我近期在研究一个 NLP 项目,根据项目的要求,需要能够通过设计算法和模型处理单词的音节 (Syllables),并对那些没有在词典中出现的单词找到其在词典中对...

762
来自专栏算法channel

机器学习|聚类算法之DBSCAN

DBSCAN,全称:Density-Based Spatial Clustering of Applications with Noise,是一个比较有代表性的...

3859
来自专栏tkokof 的技术,小趣及杂念

对于"矩阵连乘问题"的一点想法

在算法设计的学习中,每到“动态规划”一节,一般都会涉及到“矩阵连乘”问题(例如《Algorithms》,中文译名《算法概论》),可想而知该题的经典程度 :)

873
来自专栏专知

【论文推荐】最新十篇机器翻译相关论文—记忆增强、词嵌入、形态学信息、非自回归神经序列、用户反馈、语法纠错、单语语料、自注意力机制

2142
来自专栏成长道路

降维:主成分分析(PCA)

定义:可以将特征向量投影到低维空间,实现对特征向量的降维 步骤: 1.数据预处理。这里预处理包含俩个部分:均值归一化和属性范围调整。均值归一化是相应属性减去平均...

2350
来自专栏贾志刚-OpenCV学堂

OpenCV中实现曲线与圆拟合

使用OpenCV做图像处理与分析的时候,经常会遇到需要进行曲线拟合与圆拟合的场景,很多OpenCV开发者对此却是一筹莫展,其实OpenCV中是有现成的函数来实现...

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

缺失值的处理方法

对于数据挖掘和分析人员来说,数据准备(Data Preparation,包括数据的抽取、清洗、转换和集成)常常占据了70%左右的工作量。而在数据准备的过程中...

4319

扫码关注云+社区