Luogu P4316 绿豆蛙的归宿//期望

这道题没啥好讲的 就是拿个样例出来画画图推个公式 就行

倒着打公式是友好的，正着打公式是不友好的

但是蒟蒻是正着打的公式......而且还错了

推了正确式子之后发现反向建边就可以了......真是tricky

上错代码

#include<bits/stdc++.h>

using namespace std ;

const int MAXN = 100010, MAXM = 200010;
int rd[MAXN],cd[MAXN],n,m;
double ans[MAXN],anss[MAXN];
queue<int> que;

struct Edge{
    int to,nxt,dis;
}edge[MAXM];
int head[MAXN],ectr;
void addedge(int from,int to,int dis) {
    ectr++;rd[to]++,cd[from] ++ ;
    edge[ectr].dis = dis;
    edge[ectr].to = to;
    edge[ectr].nxt = head[from];
    head[from] = ectr;
}

void topo(){
    int st,fi;
    for(int i=1;i<=n;i++){
        if(rd[i] == 0) st = i;
        if(cd[i] == 0) fi = i;
    }
//    cout<<st << " " << fi<<endl;
    que.push(st);
    while(!que.empty()){
        int x = que.front();
        que.pop();
        for(int i = head[x];i;i = edge[i].nxt) {
            int y = edge[i].to;++ans[y];
            anss[y] += anss[x] + edge[i].dis;
            if(ans[y] == rd[y]){
                anss[y] = anss[y] * 1.0 / rd[y];
                que.push(y);
            }
        }
    }
//    for(int i=1;i<=n;i++){
//        cout<<rd[i]<<" "<<cd[i]<<endl;
//        cout<<"ans"<<i<<" = ";
//        printf("%.3lf
",anss[i]);
//    }
    printf("%.2lf",anss[fi]);
    return ;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        addedge(b,a,c);//我就改了这一处就WA变AC
    }
    topo();
    return 0;
}

TAG： SIN_XIII ⑨