floyd...求最短路時順便求出路徑數. 時間復雜度O(N^3)?

-------------------------------------------------------------------------------------------

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;typedef long long ll;const int maxn = 109;const int INF = 0X3F3F3F3F;int N, d[maxn][maxn];ll cnt[maxn][maxn];int main() {int m;scanf("%d%d", &N, &m);for(int i = 0; i < N; i++) {for(int j = 0; j < N; j++)d[i][j] = INF, cnt[i][j] = 0;d[i][i] = 1;cnt[i][i] = 1;}while(m--) {int u, v, w;scanf("%d%d%d", &u, &v, &w);u--, v--;d[u][v] = d[v][u] = w;cnt[u][v] = cnt[v][u] = 1;}for(int k = 0; k < N; k++)for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)if(d[i][k] + d[k][j] < d[i][j]) {d[i][j] = d[i][k] + d[k][j];cnt[i][j] = cnt[i][k] * cnt[k][j];} else if(d[i][k] + d[k][j] == d[i][j])cnt[i][j] += cnt[i][k] * cnt[k][j];for(int k = 0; k < N; k++) {double ans = 0;for(int i = 0; i < N; i++)for(int j = 0; j < N; j++) if(d[i][j] != INF)if(d[i][k] + d[j][k] == d[i][j])ans += (double) cnt[i][k] * cnt[j][k] / cnt[i][j];printf("%.3lf\n", ans);} return 0;}

-------------------------------------------------------------------------------------------

1491: [NOI2007]社交網絡

Time Limit:?10 Sec??Memory Limit:?64 MB
Submit:?1271??Solved:?727
[Submit][Status][Discuss]

Description

Input

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

Source

?

轉載于:https://www.cnblogs.com/JSZX11556/p/5147891.html

總結

以上是生活随笔為你收集整理的BZOJ 1491: [NOI2007]社交网络( floyd )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。