Bzoj 1491(最短路+乘法原理)

BZOJ 1491
之前一直想dij/SPFA,被次短路的思路越扯越远…看见$n$才$100$那就应该想Floyd啊。。题目挺水虽然说NOI原题。。
Floyd时顺便求路径条数,用乘法原理$num(i,j)=num(i,k) \times num(k,j)$,相同的时候不要忘了加上$num(i,k) \times num(k,j)$
之后再扫一次,找每个中转点$k$,然后继续用乘法原理,经过$k$点的路径总数为$num(i,k) \times num(k,j)$,然后统计一下就出来了

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
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
const int INF = 1000000000;
int n, m;
int G[MAXN][MAXN];
double num[MAXN][MAXN], imp[MAXN];
void clean() {
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) G[i][j] = INF, num[i][j] = 1.0;
imp[i] = 0.0;
}
}
void solve() {
clean();
for (int i=1;i<=m;i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
G[a][b] = G[b][a] = c;
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i != j && i != k && j != k && G[i][k] != INF && G[k][j] != INF) {
if (G[i][j] > G[i][k] + G[k][j]) {
G[i][j] = G[i][k] + G[k][j];
num[i][j] = num[i][k] * num[k][j];//乘法原理
} else if (G[i][j] == G[i][k] + G[k][j]) num[i][j] += num[i][k] * num[k][j];//加法原理,不要忘了加
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i != j && i != k && j != k && G[i][k] != INF && G[k][j] != INF && G[i][j] != INF) {
if (G[i][j] == G[i][k] + G[k][j]) imp[k] += (num[i][k] * num[k][j]) / num[i][j];
}
for (int i=1;i<=n;i++) printf("%.3f\n", imp[i]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------