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

题解 :

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

推导:

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

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]);}