luogu P2047 社交网络

P2047 社交网络

2017-09-17


题目描述

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

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

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

令Cs,t表示从s到t的不同的最短路的数目,Cs,t(v)表示经过v从s到t的最短路的数目;则定义

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

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

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


输入输出格式

输入格式:

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

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

输出格式:

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


输入输出样例

输入样例#1:

4 4
1 2 1
2 3 1
3 4 1
4 1 1

输出样例#1:

1.000
1.000
1.000
1.000

说明

对于1号结点而言,只有2号到4号结点和4号到2号结点的最短路经过1号结点,而2号结点和4号结点之间的最短路又有2条。因而根据定义,1号结点的重要程度计算为1/2+1/2=1。由于图的对称性,其他三个结点的重要程度也都是1。

50%的数据中:n ≤10,m ≤45

100%的数据中:n ≤100,m ≤4 500,任意一条边的权值c是正整数,满足:1 ≤c ≤1 000。

所有数据中保证给出的无向图连通,且任意两个结点之间的最短路径数目不超过10^10。



神奇的题,Floyd很神奇的x

跑Floyd的时候顺便求一遍方案数.每个贡献是左边*右边;

最短长度改变记得清零

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
int read(){
    char ch=getchar();
    int an=0,f=1;
    while(!(‘0‘<=ch&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(‘0‘<=ch&&ch<=‘9‘){an=an*10+ch-‘0‘;ch=getchar();}
    return an*f;
}
const int maxn=200;
const ll INT=(ll)1e15+7;
using namespace std;
ll w[maxn][maxn];
ll x,y,z;
int n,m;
ll b[maxn][maxn];
double f,ans[maxn];
int main(){
    for(int i=1;i<=109;i++)
        for(int j=1;j<=109;j++)b[i][j]=INT;
    for(int i=1;i<=109;i++)b[i][i]=0;
    n=read();m=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        b[x][y]=min(z,b[x][y]);
        b[y][x]=min(z,b[y][x]);
        w[x][y]=1;w[y][x]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            if(i!=j&&j!=k&&k!=i){
                if(b[i][j]>b[i][k]+b[k][j]){
                    b[i][j]=b[i][k]+b[k][j];
                    w[i][j]=w[i][k]*w[k][j];
                }
                else if(b[i][j]==b[i][k]+b[k][j]){
                   w[i][j]+=w[i][k]*w[k][j];
                }
            }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&j!=k&&k!=i){
                if(b[i][j]==b[i][k]+b[k][j])
                ans[k]+=(double)w[i][k]*w[k][j]/w[i][j];
            }
    }
    for(int i=1;i<=n;i++)printf("%0.3f\n",ans[i]);
    return 0;
}

Floyd

by:s_a_b_e_r



我感觉我仿佛没学过floyd

先跑一遍floyd求出两点之间的最短路,顺便求出两点之间的最短路数目

然后跑一个伪·floyd,找出从i到j的各条最短路中有几条是经过v的

还是那三重循环就可以做到

最后统计一发答案就可以了

具体实现方法看代码吧w

以及这竟然是道NOI题……?

#include<iostream>
#include<cstdio>
using namespace std;
const int N=109;
int n,m,cnt,p[N];
double imp[N],w[N][N],f[N][N];
void floyd()
{
     for(int k=1;k<=n;++k)
     for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j)
     if(k!=i&&i!=j&&k!=j)
     {
       if(f[i][k]+f[k][j]==f[i][j])
         w[i][j]+=w[i][k]*w[k][j];
       if(f[i][k]+f[k][j]<f[i][j])
       {
         w[i][j]=w[i][k]*w[k][j];
         f[i][j]=f[i][k]+f[k][j];
       }
     }
}
void solve()
{
     for(int k=1;k<=n;++k)
     for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j)
     if(k!=i&&i!=j&&k!=j)
     {
       if(f[i][j]==f[i][k]+f[k][j])
       imp[k]+=w[i][k]*w[k][j]/w[i][j];
     }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)f[i][j]=1e9+7;
    for(int i=1;i<=n;++i)f[i][i]=0;
    for(int i=1;i<=m;++i)
    {
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      f[x][y]=z;w[x][y]=1;
      f[y][x]=z;w[y][x]=1;
    }
    floyd();
    solve();
    for(int i=1;i<=n;++i)printf("%.3f\n",imp[i]);
    return 0;
}

social network

by;wypx


时间: 09-17

luogu P2047 社交网络的相关文章

洛谷——P2047 社交网络

P2047 社交网络 题目描述 在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象.不妨看这样的一个问题.在一个社交圈子里有n个人,人与人之间有不同程度的关系.我 们将这个关系网络对应到一个n个结点的无向图上,两个不同的人若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值c,c越小,表示两 个人之间的关系越密切. 我们可以用对应结点之间的最短路长度来衡量两个人s和t之间的关系密切程度,注意到最短路径上的其他结点为s和t的联系提供了某种便利

洛谷—— P2047 社交网络

https://www.luogu.org/problem/show?pid=2047 题目描述 在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象.不妨看这样的一个问题.在一个社交圈子里有n个人,人与人之间有不同程度的关系.我 们将这个关系网络对应到一个n个结点的无向图上,两个不同的人若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值c,c越小,表示两 个人之间的关系越密切. 我们可以用对应结点之间的最短路长度来衡量两个人s和t之间的关

luogu P3799 妖梦拼木棒

二次联通门 : luogu P3799 妖梦拼木棒 /* luogu P3799 妖梦拼木棒 用一个桶存下所有的木棒 美剧两根短的木棒长度 后随便乘一乘就 好了.. */ #include <algorithm> #include <cstdio> #define Mod 1000000007 #define Max 5000 void read (int &now) { now = 0; register char word = getchar (); while (wo

[luogu P1967][NOIp2013]P1967 货车运输

题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 输入输出格式 输入格式: 输入文件名为 truck.in. 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道 路. 接下来 m 行每行 3 个整数 x. y. z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z

luogu 3126 回文的路径

https://www.luogu.org/problem/show?pid=3126 考虑dp,从两头走到中间. f[i][j][k][l]表示从左上角走到(i,j),从右下角走到(k,l),路径长度相等,所经过路径相同的方案数. 方程不再赘述. 考虑步数要相同,所以只要枚举步数和行就好. f[i][j][k]表示第一个点在第j行,第2个点在第k行,走i步的方案数. 所以得出方程f[i][j][k]=(f[i-1][j-1][k]+f[i-1][j][k+1]+f[i-1][j-1][k+1]

luogu P2018 消息传递

二次联通门 : luogu P2018 消息传递 /* luogu P2018 消息传递 树形dp 原来用优先队列做了一下, T了俩点 MMP 去看正解.. 复杂度一样好不好.. 每次到达一个点,记录其子树中所有的dp值 优先向大的一边转移 */ #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define INF 1e8 const int BUF

luogu P1966 火柴排队

二次联通门 : luogu P1966 火柴排队 /* luogu P1966 火柴排队 神TM逆序对... noip怎么这么坑啊.. 暴力都没得打 此题模拟考试时爆了0 做法 将A数组排序,由于B数组与A数组是一一对应的 那么B数组的位置也会发生相应的变化 此时B数组逆序数对数即为答案 */ #include <cstdio> #include <iostream> #include <algorithm> const int BUF = 123123123; cha

luogu P1941 飞扬的小鸟

二次联通门 : luogu P1941 飞扬的小鸟 /* luogu P1941 飞扬的小鸟 dp 向上飞是完全背包,向下掉就是01背包 分情况讨论一下 最后合并一下 */ #include <cstdio> #include <iostream> #include <cstring> const int BUF = 123123123; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (

luogu P2863 [USACO06JAN]牛的舞会The Cow Prom

https://www.luogu.org/problem/show?pid=2863#sub 题目描述 The N (2 <= N <= 10,000) cows are so excited: it's prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform th