BZOJ-1491 社交网络题解(Floyd)

Description

传送门:BZOJ-1491

在社交网络(socialnetwork)的研究中,我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题。

在一个社交圈子里有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)有意义,我们规定需要处理的社交网络都是连通的无向图

,即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图,请你求出每

一个结点的重要程度。


Input

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

。接下来m行,每行用三个整数a,b,c描述一条连接结点a和b,权值为c的无向边。注意任意两个结点之间最多有

一条无向边相连,无向图中也不会出现自环(即不存在一条无向边的两个端点是相同的结点)。n≤100;m≤4500

,任意一条边的权值 c 是正整数,满足:1≤c≤1000。所有数据中保证给出的无向图连通,且任意两个结点之间

的最短路径数目不超过 10^10

Output

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

Sample Input

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

Sample Output

1
2
3
4
1.000
1.000
1.000
1.000

题目大意

给出一个无向图根据上面的公式求出每个点的重要程度。公式的意思就是对于任意一个起点s到任意一个终点t的最短路中经过v点的最短路数量占总共s到t的最短路数量的比值相加。

思路

因为数据只有100所以我们可以使用floyd来记录任意两点之间的最短路和最短路数量,对于任意一个点v,如果dis[s][t]=dis[s][v]+dis[v][t],那么这个点v就一定在s到t的最短路上,根据乘法原理,那么s-t这对起终点对v的贡献就是num[s][v]*num[v][t]/num[s][t],然后对于每一个点输出答案就行了,但是需要注意的是如果两个点直接相连就不能被记录。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/************************************************************
> File Name: 1491.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Mon 25 Nov 2019 11:05:42 PM CST
************************************************************/

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc (o<<1)
#define rc (o<<1|1)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e2+5;
const int MAXM = 2e5+5;
const int MOD = 1e9+7;
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
const double PI = acos(-1.0);
const double EXP = 1e-8;
int w[MAXN][MAXN];
double num[MAXN][MAXN];
double ans[MAXN];
int main(void){
int n, m, x, y, z;
scanf("%d%d",&n,&m);
memset(w,127/3,sizeof w);
for(int i = 1;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
w[x][y] = w[y][x] = z;
num[x][y] = num[y][x] = 1;
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
if(i==k)
continue;
for(int j = 1;j <= n;j++){
if(j==k || j==i)
continue;
if(w[i][j] > w[i][k]+w[k][j]){
w[i][j] = w[i][k]+w[k][j];
num[i][j] = num[i][k]*num[k][j];
}else if(w[i][j]==w[i][k]+w[k][j])
num[i][j] += num[i][k]*num[k][j];
}
}
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
if(i==k)
continue;
for(int j = 1;j <= n;j++){
if(j==k||j==i)
continue;
if(w[i][j]==w[i][k]+w[k][j])
ans[k] += ((num[i][k]*num[k][j])/num[i][j]);
}
}
printf("%.3lf\n",ans[k]);
}
return 0;
}

本文标题:BZOJ-1491 社交网络题解(Floyd)

文章作者:TSwifite

发布时间:2019年11月29日 - 13:11

最后更新:2019年11月29日 - 13:11

原始链接:http://tswiftie.com/BZOJ-1491-社交网络题解-Floyd/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%