bzoj1491: [NOI2007]社交网络 | jeffswt: the ac moments

Description

在社交网络 (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 \neq v, t \neq v} \frac{C_{s,t}(v)}{C_{s,t}} \] 为结点 \(v\) 在社交网络中的重要程度.

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

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

Input

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

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

Output

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

Sample Input

Sample Output

Data Range

50% 的数据中:\(n \leq 10, m \leq 45\)

100% 的数据中:\(n \leq 100, m \leq 4500\), 任意一条边的权值 \(c\) 是正整数, 满足:\(1 \leq c \leq 1 000\).

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

Explanation

首先应该直观反映得到的就是应该上 Floyd 求多源最短路. 具体地, 应该维护任意两个点之间有多少条最短路:\[ cnt[i][j] = \sum_{1 \leq k \leq n}^{dist[i][k] + dist[k][j] = dist[i][j]} cnt[i][k] \cdot cnt[k][j] \] 然后针对每一个节点就有显然的权重了:\[ I(k) = \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{cnt[i][k] \cdot cnt[k][j]}{cnt[i][j]}\ \text{if}\ dist[i][k] + dist[k][j] = dist[i][j] \] 这个应该比较简单吧, 毕竟是第一道题......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 110;
const llf infinit = 1e15;

class FloydShortestPath
{
public:
    int n;
    llf dist[maxn][maxn];
    llf cnt[maxn][maxn];
    void add_edge(int u, int v, llf len)
    {
        dist[u][v] = dist[v][u] = len;
        cnt[u][v] = cnt[v][u] = 1;
    }
    void init(void)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = infinit;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cnt[i][j] = 0;
        return ;
    }
    void eval(void)
    {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        cnt[i][j] = 0;
                    } if (dist[i][k] + dist[k][j] == dist[i][j]) { // No else!
                        cnt[i][j] += cnt[i][k] * cnt[k][j];
                    }
                }
        for (int i = 1; i <= n; i++)
            cnt[i][i] = 0;
        return ;
    }
} graph;

int n, m;
llf res[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    graph.init();
    for (int i = 1, a, b; i <= m; i++) {
        llf c = 0;
        scanf("%d%d%lf", &a, &b, &c);
        graph.add_edge(a, b, c);
    }
    // Executing floyd algorithm
    graph.eval();
    // Extracting answers
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (graph.dist[i][j] == graph.dist[i][k] + graph.dist[k][j] && graph.cnt[i][j] > 0)
                    res[k] += graph.cnt[i][k] * graph.cnt[k][j] / graph.cnt[i][j];
    // Output answers
    for (int k = 1; k <= n; k++)
        printf("%.3lf\n", res[k]); // 3 digits, not 6...
    return 0;
}