The Preliminary Contest for ICPC Asia Nanjing 2019 - D Robots（概率dp+拓扑排序）

这题概率dp + 拓扑排序可以写

改天补解释

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

vector<int>vec[maxn];

int indeg[maxn],seq[maxn];

double d[maxn],f[maxn];

int N,M,T,tot=0;

void topo()

{

    queue<int>q;

    q.push(1);

    tot=0;

    seq[tot++]=1;

    while (!q.empty()) {

        int u=q.front();

        q.pop();

        for (int i=0;i<vec[u].size();i++) {

            if (--indeg[vec[u][i]]==0) {

                q.push(vec[u][i]);

                seq[tot++]=vec[u][i];

            }

        }

    }

}

int main()

{

    scanf("%d",&T);

    while (T--) {

        scanf("%d%d",&N,&M);

        for (int i=1;i<=N;i++) {

            vec[i].clear();

        }

        memset(indeg,0,sizeof(indeg));

        for (int i=0;i<=N;i++) {

            d[i]=0;

            f[i]=0;

        }

        int x,y;

        for(int i=0;i<M;i++) {

            scanf("%d%d",&x,&y);

            vec[x].push_back(y);

            indeg[y]++;

        }

        topo();

        for (int i=tot-2;i>=0;i--) {

            int u=seq[i];

            int cnt=vec[u].size()+1;

            for (int j=0;j<cnt-1;j++) {

                d[u]+=d[vec[u][j]];

            }

            d[u]=(d[u]/(double)cnt+1)*(double)cnt/(double)(cnt-1);

        }

        for (int i=tot-2;i>=0;i--) {

            int u=seq[i];

            int cnt=vec[u].size()+1;

            for (int j=0;j<cnt-1;j++) {

                f[u]+=f[vec[u][j]];

            }

            f[u]+=cnt*d[u];

            f[u]=f[u]/(double)(cnt-1);

        }

        printf("%.2lf\n",f[1]);

    }

    return 0;

}