题目大意
给定 n 个点、m 条无向带权边的图,定义一个顶点的重要度为:
I(u)=s=u&t=u∑Cs,tCs,t(u)
其中,Cs,t 表示 s、t 之间的最短路数量,Cs,t(u) 表示其中经过 u 的数量。
求每个节点的重要度。
1⩽n⩽100
1⩽wi⩽1,000 (边权)
1⩽Cs,t⩽10,000,000,000
题目链接
【NOI 2007】社交网络
题解
边 Floyd 边计算经过某个节点的最短路数量。
注意,disti,i 最好设为大于 0 的数,不然一个节点自已会把答案更新得特别大。。。
代码
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
| #include <cstdio> #include <climits> const int MAXN = 105; int main() { int n, m; scanf("%d %d", &n, &m); static long long cnt[MAXN][MAXN]; static int dist[MAXN][MAXN]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cnt[i][j] = 0; dist[i][j] = INT_MAX / 2; } cnt[i][i] = 1; dist[i][i] = 1; } for (int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); dist[v][u] = dist[u][v] = w; cnt[v][u] = cnt[u][v] = 1; } 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] = cnt[i][k] * cnt[k][j]; } else if (dist[i][k] + dist[k][j] == dist[i][j]) cnt[i][j] += cnt[i][k] * cnt[k][j]; } for (int k = 1; k <= n; k++) { double ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dist[i][k] + dist[k][j] == dist[i][j]) ans += (double) cnt[i][k] * cnt[k][j] / cnt[i][j]; printf("%.3lf\n", ans); } return 0; }
|