題意翻譯

「Poetize3」

題目背景

隨著新版百度空間的上線，Blog寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。

題目描述

給出一個有向無環圖，起點為1終點為N，每條邊都有一個長度，并且從起點出發能夠到達所有的點，所有的點也都能夠到達終點。綠豆蛙從起點出發，走向終點。 到達每一個頂點時，如果有K條離開該點的道路，綠豆蛙可以選擇任意一條道路離開該點，并且走向每條路的概率為 1/K 。 現在綠豆蛙想知道，從起點走到終點的所經過的路徑總長度期望是多少？

輸入輸出格式

輸入格式：

?

第一行: 兩個整數 N M，代表圖中有N個點、M條邊 第二行到第 1+M 行: 每行3個整數 a b c，代表從a到b有一條長度為c的有向邊

?

輸出格式：

?

從起點到終點路徑總長度的期望值，四舍五入保留兩位小數。

?

輸入輸出樣例

輸入樣例#1：?復制

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

輸出樣例#1：?復制

7.00

說明

對于20%的數據 N<=100

對于40%的數據 N<=1000

對于60%的數據 N<=10000

對于100%的數據 N<=100000，M<=2*N

?

直接利用期望的定義推就行。

不過正著推非常不好寫

我是建反圖推的

?

// 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;
inline int read() {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];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z)  {E[num] = (Edge) {x, y, z, head[x]};head[x] = num++;
}
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);
#endifmemset(head, -1, sizeof(head));N = read(); M = read();for(int i = 1; i <= M; i++) {int x = read(), y = read(), z = read();swap(x, y);AddEdge(x, y, z);inder[y]++; inder2[y]++;}Topsort();printf("%.2lf", dis[1]);return 0;
}   

?

轉載于:https://www.cnblogs.com/zwfymqz/p/9287217.html

總結

以上是生活随笔為你收集整理的洛谷P4316 绿豆蛙的归宿(期望)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。