[Solution][Graph Theory][Floyed]NOI2007 Network

【题目】

戳这里

【题意】

自行脑补。

【思路】

显然只要求出任意两点间最短路径条数即可。记之间的最短路径条数。
那么对于一个点i,枚举所有其他任意两个点j,k,如果这个点在那两个点的最短路上,则重要度加上
.
注意枚举的顺序问题和重复问题。(至今不明觉厉。。。好在记住了。。。)

【代码】

#include<cstdio>
#include<cstring>
const int N = 101;
int g[N][N];
long long num[N][N];
int main()
{
    int n , m;
    scanf("%d%d" , &n , &m);
    register int i , j , k;
    memset(g , 0x3f , sizeof(g));
    for(i = 1 ; i <= n ; ++i)
        g[i][i] = 0;
    int a , b , x;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d" , &a , &b , &x);
        g[a][b] = g[b][a] = x;
        num[a][b] = num[b][a] = 1;
    }
    for(k = 1 ; k <= n ; ++k)
    {
        for(i = 1 ; i <= n ; ++i)
        {
            if (i == k)
                continue;
            for(j = i + 1 ; j <= n ; ++j)
            {
                if (j == i || j == k)
                    continue;
                if (g[i][k] + g[k][j] < g[i][j])
                {
                    g[i][j] = g[i][k] + g[k][j];
                   g[j][i] = g[i][j];
                    num[i][j] = num[i][k] * num[k][j];
                   num[j][i] = num[i][j];
                }
                else if (g[i][k] + g[k][j] == g[i][j])
                {
                    num[i][j] += num[i][k] * num[k][j];
                    num[j][i] = num[i][j];
                }
            }
        }
    }
    double ans = 0;
    for(i = 1 ; i <= n ; ++i)
    {
        ans = 0;
        for(j = 1 ; j <= n ; ++j)
        {
            if (j == i)
                continue;
            for(k = 1 ; k <= n;  ++k)
            {
                if (k == i || k == j)
                    continue;
                if (g[j][i] + g[i][k] == g[j][k])
                    ans += num[j][i] * num[i][k] / double(num[j][k]);
            }
        }
        printf("%.3lf\n" , ans);
    }
    return 0;
}
comments powered by Disqus