[Ctsc2015]misc

蔚落 2022-01-06 15:59 245阅读 0赞

[https://lydsy.com/JudgeOnline/problem.php?id=4055][https_lydsy.com_JudgeOnline_problem.php_id_4055]

#### 题解 ####

观察题目要我们求的东西：  
\\\[ ans\[k\]=\\sum\_\{i\}\\sum\_j \\frac\{a\_i\*a\_j\*f\_k\[i\]\[j\]\}\{f\[i\]\[j\]\} \\\]  
然后我们可以先枚举i，然后对于那个带限制的最短路部分，我们可以把贡献拆成两部分来计算。  
\\\[ ans\[k\]=\\sum\_\{i\}a\_i\*f\[i\]\[k\]\\sum\_j\\frac\{a\_j\*f\[k\]\[j\]\}\{f\[i\]\[j\]\} \\\]  
由于我们还要满足最短路的限制，所以我们可以先对每个i建出以i为源点的最短路\\(DAG\\)然后再\\(DAG\\)上维护后面的求和就可以了，这样可以保证是合法的。

##### Warning #####

维护f数组时注意一开始为了转移将\\(f\[i\]\[i\]=1\\)，最后做完了记得清空。

#### 代码 ####

#include<bits/stdc++.h>
    #define N 1009
    #define M 4009
    #define mm make_pair
    using namespace std;
    typedef long long ll;
    int head[N],tot,dis[N],du[N],n,m;
    bool vis[N];
    vector<int>vec[N];
    vector<int>::iterator it;
    priority_queue<pair<int,int> >q; 
    long double cnt[N][N],g[N],ans[N],a[N];
    inline ll rd(){
        ll x=0;char c=getchar();bool f=0;
        while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
        while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
        return f?-x:x;
    }
    struct edge{
        int n,to,l;double f;
    }e[M<<1];
    inline void add(int u,int v,int l,double f){
        e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].f=f;e[tot].l=l;
    }
    inline void link(int i,int u){
        vec[u].push_back(i);du[e[i].to]++;
    }
    inline void dij(int s){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        q.push(mm(0,s));cnt[s][s]=1;dis[s]=0;
        while(!q.empty()){
            int u=q.top().second;q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=head[u];i;i=e[i].n){
                int v=e[i].to;
                if(dis[v]>dis[u]+e[i].l){
                    dis[v]=dis[u]+e[i].l;
                    cnt[s][v]=cnt[s][u]*e[i].f; 
                    q.push(mm(-dis[v],v));
                }
                else if(dis[v]==dis[u]+e[i].l)cnt[s][v]+=cnt[s][u]*e[i].f;
            }
        }
    }
    inline void topsort(int s){
        memset(g,0,sizeof(g));
        queue<int>q;
        for(int i=1;i<=n;++i)if(!du[i])q.push(i);
        while(!q.empty()){
            int u=q.front();q.pop();
            ans[u]+=a[s]*cnt[s][u]*g[u];
            g[u]+=a[u]/cnt[s][u];
            for(it=vec[u].begin();it!=vec[u].end();++it){
                int i=*it,v=e[i].to;
                if(!--du[v])q.push(v);
                g[v]+=g[u]*e[i].f;
            }
        }
    }
    int main(){
        n=rd();m=rd();
        for(int i=1;i<=n;++i)a[i]=rd();
        int u,v,l;double f;tot=1;
        for(int i=1;i<=m;++i){
            u=rd();v=rd();l=rd();scanf("%lf",&f);
            add(u,v,l,f);add(v,u,l,f);
        }
        for(int s=1;s<=n;++s){
            dij(s);
            cnt[s][s]=0;
            for(int u=1;u<=n;++u)
              for(int i=head[u];i;i=e[i].n)if(dis[u]+e[i].l==dis[e[i].to])link(i^1,e[i].to);
            topsort(s);
            for(int u=1;u<=n;++u)vec[u].clear();
        }
        for(int i=1;i<=n;++i)printf("%.8Lf\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/ZH-comld/p/10816244.html

[https_lydsy.com_JudgeOnline_problem.php_id_4055]: https://lydsy.com/JudgeOnline/problem.php?id=4055