# 洛谷P4316 绿豆蛙的归宿(期望)

「Poetize3」

4 4
1 2 1
1 3 2
2 3 3
3 4 4

7.00

## 说明

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define LL long long
using namespace std;
const int MAXN = 200000, INF = 1e9 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
struct Edge {
int u, v, w, nxt;
}E[MAXN];
inline void AddEdge(int x, int y, int z)  {
E[num] = (Edge) {x, y, z, head[x]};
}
double inder[MAXN], dis[MAXN], inder2[MAXN];
void Topsort() {
queue<int> q;
for(int i = 1; i <= N; i++)
if(inder[i] == 0)
q.push(i);
while(!q.empty()) {
int p = q.front(); q.pop();
//if(p != x) dis[p] = dis[p] / inder2[p];
for(int i = head[p]; ~i; i = E[i].nxt) {
int to = E[i].v;
dis[to] += (dis[p] + E[i].w) / inder2[to];
inder[to]--;
if(!inder[to]) q.push(to);
}

//dis[p] /= inder2[p];
//printf("%d %lf %lf\n", p, dis[p], inder2[p]);
}
}
main() {
#ifdef WIN32
//freopen("a.in", "r", stdin);
#endif
for(int i = 1; i <= M; i++) {
swap(x, y);
inder[y]++; inder2[y]++;
}
Topsort();
printf("%.2lf", dis[1]);
return 0;
}

1811 篇文章121 人订阅

0 条评论

## 相关文章

28130

24810

### 100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一，非常适合刚学习完Numpy基础的同学，完成以下习题可以帮助你更好的掌握这个基础库。

620100

791120

33850

7410

15920

14210

45340

1.5K80