P2047 [NOI2007]社交网络

题目描述

在社交网络（\(social\) \(network\)）的研究中，我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题。在一个社交圈子里有\(n\)个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个\(n\)个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值\(c\)，\(c\)越小，表示两个人之间的关系越密切。

我们可以用对应结点之间的最短路长度来衡量两个人\(s\)和\(t\)之间的关系密切程度，注意到最短路径上的其他结点为\(s\)和\(t\)的联系提供了某种便利，即这些结点对于\(s\)和\(t\)之间的联系有一定的重要程度。我们可以通过统计经过一个结点\(v\)的最短路径的数目来衡量该结点在社交网络中的重要程度。

考虑到两个结点\(A\)和\(B\)之间可能会有多条最短路径。我们修改重要程度的定义如下：

令\(C_{s,t}\)表示从\(s\)到\(t\)的不同的最短路的数目，\(C_{s,t(v)}\)表示经过\(v\)从\(s\)到\(t\)的最短路的数目；则定义

\(I(v)=\sum_{s!=v,t!=v} C_{s,t(v)}/C_{s,t}\)

为结点\(v\)在社交网络中的重要程度。

为了使\(I(v)\)和\(C_{s,t(v)}\)有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。

现在给出这样一幅描述社交网络s的加权无向图，请你求出每一个结点的重要程度。

输入输出格式

输入格式：

输入第一行有两个整数，\(n\)和\(m\)，表示社交网络中结点和无向边的数目。在无向图中，我们将所有结点从1到\(n\)进行编号。

接下来\(m\)行，每行用三个整数\(a\),\(b\),\(c\)描述一条连接结点\(a\)和\(b\)，权值为\(c\)的无向边。注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

输出格式：

输出包括\(n\)行，每行一个实数，精确到小数点后3位。第\(i\)行的实数表示结点\(i\)在社交网络中的重要程度

这是一道最短路计数+枚举的题目。

提供一种disj的最短路计数思路。

当某个点已经松弛完毕，去松弛其他点时，若松弛成功，则将计数改为这个点的计数，若不成功但权值与对方相等，则把自己的计数加上去。

最后枚举每个点，看是否在\(s,t\)的最短路上，如果在，用乘法原理计算即可。

Code:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#define P pair<int,int >

#define ll long long

using namespace std;

const int N=102;

const int M=9020;

int head[N],edge[M],to[M],next[M],cnt0;

void add(int u,int v,int w)

{

    to[++cnt0]=v;edge[cnt0]=w;next[cnt0]=head[u];head[u]=cnt0;

    to[++cnt0]=u;edge[cnt0]=w;next[cnt0]=head[v];head[v]=cnt0;

}

priority_queue <P,vector <P >,greater<P> > q;

P p;int n,m;ll cnt[N][N];

int dis[N][N],used[N];

void disj(int s)

{

    memset(used,0,sizeof(used));

    dis[s][s]=0;

    cnt[s][s]=1;

    p.first=0,p.second=s;

    q.push(p);

    while(!q.empty())

    {

        int u=q.top().second;

        q.pop();

        if(used[u]) continue;

        used[u]=1;

        for(int i=head[u];i;i=next[i])

        {

            int v=to[i],w=edge[i];

            if(dis[s][v]>dis[s][u]+w)

            {

                dis[s][v]=dis[s][u]+w;

                cnt[s][v]=cnt[s][u];

                p.first=dis[s][v],p.second=v;

                q.push(p);

            }

            else if(dis[s][v]==dis[s][u]+w)

                cnt[s][v]+=cnt[s][u];

        }

    }

    cnt[s][s]=0;

}

int main()

{

    scanf("%d%d",&n,&m);

    int u,v,w;

    for(int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

    memset(dis,0x3f,sizeof(dis));

    for(int i=1;i<=n;i++)

        disj(i);

    for(int k=1;k<=n;k++)

    {

        double ans=0.0;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                if(cnt[i][j]&&dis[i][k]+dis[k][j]==dis[i][j])

                    ans+=double(cnt[i][k]*cnt[k][j])/double(cnt[i][j]);

        printf("%.3lf\n",ans);

    }

    return 0;

}

2018.7.1

巴特西

洛谷 P2047 [NOI2007]社交网络解题报告

P2047 [NOI2007]社交网络

题目描述

输入输出格式

输入格式：

输出格式：

最新文章

热门文章

巴特西

洛谷 P2047 [NOI2007]社交网络 解题报告

P2047 [NOI2007]社交网络

题目描述

输入输出格式

输入格式：

输出格式：

最新文章

热门文章

洛谷 P2047 [NOI2007]社交网络解题报告