[NOI 2007]社交网络

Description

在社交网络（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

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

Sample Output

1.000
1.000
1.000
1.000

HINT

社交网络如下图所示。

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

题解

从数据约定来看,$n<=100$,明显可以用$floyd$,而且题目要求算某个中间点的重要程度,也比较符合$floyd$以中间点划分阶段的思想。
这道题主要就是要推理出最短路的条数怎么算。
令$w[i,j]$为从点$i$到点$j$的最短路径条数,$f[i,j]$为最短路。则根据最短路径拥有最优子结构的性质和乘法原理,我们可以得出:
$$w[i,j]=w[i,j]+w[i,k]*w[k,j](f[i,j]=f[i,k]+f[k,j])$$
$$w[i,j]=w[i,k]*w[k,j](f[i,j]>f[i,k]+f[k,j])$$
再令$g[i,j,k]$为从点$i$到点$j$且经过点$k$的最短路径的条数。也正是根据这个最优子结构,我们又可以明白:
$$g[i,j,k]=w[i,k]*w[k,j](f[i,j]=f[i,k]=f[k,j])$$
然后根据题目所给的公式统计答案就行了。

 //It is made by Awson on 2017.9.25

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 #define Abs(x) ((x) < 0 ? (-(x)) ? (x))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = ;

 LL Read() {

     LL sum = ;

     char ch = getchar();

     while (ch < '' || ch > '') ch = getchar();

     while (ch >= '' && ch <= '') sum = (sum<<)+(sum<<)+ch-, ch = getchar();

     return sum;

 }

 LL n, m, u, v, c;

 LL f[N+][N+];

 LL cnt[N+][N+];

 double ans[N+];

 void work() {

     n = Read(), m = Read();

     memset(f, /, sizeof(f));

     while (m--) {

     u = Read(), v = Read(), c = Read();

     if (f[u][v] > c) {

         f[u][v] = f[v][u] = c;

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

     }

     else if (f[u][v] == c)

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

     }

     for (LL k = ; k <= n; k++)

     for (LL i = ; i <= n; i++)

         for (LL j = ; j <= n; j++)

         if (k != j && k != i && i != j) {

             if (f[i][k]+f[k][j] < f[i][j]) {

             f[i][j] = f[i][k]+f[k][j];

             cnt[i][j] = cnt[i][k]*cnt[k][j];

             }

             else if (f[i][k]+f[k][j] == f[i][j])

             cnt[i][j] += cnt[i][k]*cnt[k][j];

         }

     for (LL k = ; k <= n; k++)

     for (LL i = ; i <= n; i++)

         for (LL j = ; j <= n; j++)

         if (k != j && k != i && i != j)

             if (f[i][k]+f[k][j] == f[i][j])

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

     for (LL i = ; i <= n; i++)

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

 }

 int main() {

     freopen("bestlink.in", "r", stdin);

     freopen("bestlink.out", "w", stdout);

     work();

     return ;

 }