OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【NOI2007】社交网络

【题目描述】

在社交网络(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 的最短 路的数目;则定义I(v)为结点 v 在社交网络中的重要程度。 为了使 I(v)和 Cs,t(v)有意义,我们规定需要处理的社交网络都是连通的无向 图,即任意两个结点之间都有一条有限长度的最短路径。 

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

【输入】

输入中第一行有两个整数,n 和 m,表示社交网络中结点和无向边的数目。在无向图中,我们将所有结点从 1 到 n 进行编号。 接下来 m 行,每行用三个整数 a, b, c 描述一条连接结点 a 和 b,权值为 c 的无向边。注意任意两个结点之间最多有一条无向边相连,无向图中也不会出现自环(即不存在一条无向边的两个端点是相同的结点)。

【输出】

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

【输入样例】

4 4

1 2 1

2 3 1

3 4 1

4 1 1

【输出样例】

1.000

1.000

1.000

1.000

【数据范围】

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

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

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

【题解】

多源最短路,直接Floyed解决,在Floyed时稍加改动就可以求出两点之间最短路径数目了。注意这个数目是不超过10^10,但是可以超过int……

对于一对点i,j,dis[i][j]表示它们之间的最短路长度,如果一个点k满足dis[i][k]+dis[k][j]=dis[i][j],那么这个点k就一定在i,j的最短路上。若s[i][j]表示i,j之间最短路径数目,则点k对于i,j的重要程度为(s[i][k]*s[k][j])/s[i][j]。

Floyed后枚举k即可。

【代码】

Floyed和枚举都是O(n^3)。

http://paste.ubuntu.com/8032637/

评论

© OI技术宅 | Powered by LOFTER