题目传送门(BZOJ)
>原文链接<

题解 :

这可能是网上存在的第一篇题解,反正我Baidu只百度到一个,还是404

推导:

设$F[i][j]$为从$i$到$j$的最短路的宽度,那么原式即求 :

$$R(k) = \sum\limits_{i\neq j\neq k}\frac{a_i\times a_j\times F[i][k]\times F[k][j]}{F[i][j]}$$

把这个式子分开:

$$R(k) = \sum\limits_{i\neq j\neq k}a_i\times F[i][k]\times\frac{a_j\times F[k][j]}{F[i][j]}$$

对于$a_i\times F[i][k]$这个可以$O(1)$求。

DP :

对于后面的,我们则要转换枚举。

考虑枚举$i$, 设后面那部分为$g(k)$

我们首先枚举出一个$i$,并算出以它为源点的$dis$,并以此更新$F$。

顺便求出拓扑序(最短路图的拓扑序,只要在最短路中的边)。

那么对于每个$u$, $ans[u] += a_i\times F[i][u]\times g[u]$

这个$g[u]$可以通过所有$u$可以到达的点的$g$得到,

具体做法相当于把$F[k][j]$拆开成$F[k][to]$和$F[to][j]$。

更新完答案之后别忘了为了下一步的更新$g[u] += a_u\div F[i][u]$

提示 :

DP要在逆拓扑序上做,本题又卡精度又卡常,以下是几项提示 :

$ans$/边权 可以用$double$存,$F[x], G[x]$要用$long \;double$

$Dijkstra$可以在做的同时处理出$F$和拓扑序。 而$F[x]$可以只开一维,因为我们枚举的$i$

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define mp make_pair#include <queue>using namespace std;#define f2 double#define f3 long double#define rev(i, p) for(Edge *i = head[p]; i; i = i->next)const int N = 1100;struct Edge { int to, len; f3 val; Edge *next;}*head[N], e[N<<3];inline void addEdge(int x, int y, int z, f2 w) { static int _; Edge* t; t = &e[++_]; t->to = y, t->len = z, t->val = w, t->next = head[x], head[x] = t; t = &e[++_]; t->to = x, t->len = z, t->val = w, t->next = head[y], head[y] = t;}int a[N], ind[N], n, m;int q[N], l, r, dis[N];f2 ans[N];f3 g[N], f[N];priority_queue<pair<int, int> > pq;bool vis[N];void getTopp(int S) { q[r = 1] = S, l = 0; f[S] = 1; for(int i = 1; i <= n; i ++ ) rev(j, i) { if(dis[i]+j->len == dis[j->to]) ind[j->to] ++; } while(r > l) { int u = q[++l]; rev(i, u) if(dis[u]+i->len == dis[i->to]) { if(!--ind[i->to]) q[++r] = i->to; f[i->to] += f[u]*i->val; } }}void getDis(int S) { dis[S] = 0; pq.push(mp(0, S)); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; rev(i, u) if(dis[i->to] > dis[u]+i->len) { dis[i->to] = dis[u]+i->len; pq.push(mp(-dis[i->to], i->to)); } }}void getAns(int S) { for(int p = r; p > 1; p -- ) { int u = q[p]; rev(i, u) if(dis[i->to] == dis[u]+i->len) { int v = i->to; g[u] += i->val*g[v]; } ans[u] += a[S]*f[u]*g[u]; g[u] += (f3)a[u]/f[u]; }}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for(int i = 1; i <= m; i ++ ) { int x, y, z;double w; scanf("%d%d%d%lf", &x, &y, &z, &w); addEdge(x, y, z, w); } for(int i = 1; i <= n; i ++ ) { memset(f, 0, sizeof f); memset(g, 0, sizeof g); memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); getDis(i), getTopp(i), getAns(i); } for(int i = 1; i <= n; i ++ ) printf("%.8f\n", ans[i]);}