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

Kindear

发布于 2017-12-29 08:47:36

1.1K00

代码可运行

文章被收录于专栏：算法与数据结构算法与数据结构

运行总次数：0

代码可运行

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

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

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

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

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

输入格式:

输入第一行给出两个正整数N和M，其中N（≤104）是图中结点个数，顺便假设结点从1到N编号；M（≤105）是边的条数。随后的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K（≤100）以及K个结点编号，用空格分隔。

输出格式:

按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。

输入样例:

输出样例:

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)));
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-12-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据处理

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据处理

登录后参与评论

0 条评论

热度