P5882 [CTSC2015]misc

· · 题解

\begin{aligned} R(v)&=\sum_{s}\sum_{t}\frac{a_sa_t\sigma_{st}(v)}{\sigma_{st}}\\ &=\sum_s a_s \sum_t \frac{a_t \sigma_{sv}\sigma_{vt}}{\sigma_{st}}\\ &= \sum_s a_s \sigma_{sv} \sum_t \frac{a_t\sigma_{tv}}{\sigma_{st}} \end{aligned}

考虑用计算贡献的方法做。

R(v) \leftarrow a_s \sigma_{sv} \sum_t \frac{a_t\sigma_{tv}}{\sigma_{st}}

对于每一个点 s，建出以其为源点的最短路 DAG （将边反向，因为 DP 的顺序为拓扑逆序），然后 DAG 上 DP。\sigma 在求最短路的时候就能算。设 f_u=\sum_t\frac{a_t\sigma_{tv}}{\sigma_{st}}。转移为将 \sigma_{u,t}=\sigma_{u,v}\times \sigma_{v,t} ：

f_u=\frac{a_u}{\sigma_{su}}+\sum_{v\to u} f_vw_{uv}

要注意，f 包含 u=t 的情况，于是答案需要忽略这种情况。

#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1009, M=5009;
typedef pair<int,int> pii;

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt,w; double wd;} e[M*2]; int hd[N],tot=1;
void add(int u,int v,int w,double wd) {e[++tot]=(edge){v,hd[u],w,wd};hd[u]=tot;}

int n,m,d[N],deg[N],a[N];
long double sig[N],f[N],ans[N];
bool vst[N];
vector<edge>dag[N];

void dijkstra(int s) {
    priority_queue<pii>q; q.push(make_pair(0,s));
    memset(d,0x3f,sizeof(d)), memset(vst,0,sizeof(vst));
    d[s]=0, sig[s]=1;
    while(!q.empty()) {
        int u=q.top().second; q.pop();
        if(vst[u]) continue; vst[u]=1;
        for(int i=hd[u],v;i;i=e[i].nxt) {
            if(d[v=e[i].to]>d[u]+e[i].w)
                d[v]=d[u]+e[i].w, q.push(make_pair(-d[v],v)), sig[v]=sig[u]*e[i].wd;
            else if(d[v]==d[u]+e[i].w) sig[v]+=sig[u]*e[i].wd;
        }
    }
}
void topo(int s) {
    queue<int>q; memset(f,0,sizeof(f));
    rep(i,1,n) if(!deg[i]) q.push(i);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        ans[u]+=a[s]*sig[u]*f[u], f[u]+=a[u]/sig[u];
        for(auto ed:dag[u]) {
            int v=ed.to; double wd=ed.wd;
            f[v]+=f[u]*wd, deg[v]--;
            if(!deg[v]) q.push(v);
        }
    }
}

int main() {
    n=read(), m=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,m) {
        int u,v,w; double wd; scanf("%d%d%d%lf",&u,&v,&w,&wd);
        add(u,v,w,wd), add(v,u,w,wd);
    }
    rep(s,1,n) {
        dijkstra(s); sig[s]=0;
        rep(u,1,n) for(int i=hd[u],v;i;i=e[i].nxt) if(d[u]+e[i].w==d[v=e[i].to])
            dag[v].push_back(e[i^1]), deg[u]++;
        topo(s);
        rep(u,1,n) dag[u].clear();
    }
    rep(i,1,n) printf("%.6Lf\n",ans[i]);
    return 0;
}