Robots 2019南京网络赛（概率dp）

曾经终败给现在 2023-08-17 17:04 62阅读 0赞

# Robots #

\\\[ Time Limit: 1000 ms \\quad Memory Limit: 262144 kB \\\]

## 题意 ##

有一个机器人要从 \\(1\\) 点走到 \\(n\\) 点，每走一步都需要一天，并且这一步的代价是已经经过的天数。

## 思路 ##

将问题拆成两个问题，\\(dp1\[i\]\\) 表示从 \\(i\\) 到 \\(n\\) 的天数期望，\\(dp2\[i\]\\) 表示从 \\(i\\) 到 \\(n\\) 的代价期望。  
那么就很容易得到  
\\\[ dp1\[u\] = \\frac\{\\sum\_\{u->v\}(dp1\[v\]) + dp1\[u\]\}\{u.size()+1\} + 1\\\\ dp1\[u\] = \\frac\{\\sum\_\{u->v\}(dp1\[v\]) + u.size()+1\}\{u.size()\} \\\\ dp2\[u\] = \\frac\{\\sum\_\{u->v\}(dp2\[v\]) + dp2\[u\]\}\{u.size()+1\} + dp1\[u\]\\\\ dp2\[u\] = \\frac\{\\sum\_\{u->v\}(dp2\[v\]) + (u.size()+1)\*dp1\[u\]\}\{u.size()\} \\\]

/*************************************************************** > File Name : a.cpp > Author : Jiaaaaaaaqi > Created Time : Mon 09 Sep 2019 10:07:54 PM CST ***************************************************************/ #include <map> #include <set> #include <list> #include <ctime> #include <cmath> #include <stack> #include <queue> #include <cfloat> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define lowbit(x) x & (-x) #define mes(a, b) memset(a, b, sizeof a) #define fi first #define se second #define pb push_back #define pii pair<int, int> typedef unsigned long long int ull; typedef long long int ll; const int maxn = 1e5 + 10; const int maxm = 1e5 + 10; const ll mod = 1e9 + 7; const ll INF = 1e18 + 100; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-8; using namespace std; int n, m; int cas, tol, T; vector<int> vv[maxn], rv[maxn]; int ind[maxn]; double dp1[maxn], dp2[maxn]; void solve() { queue<int> q; dp1[n] = dp2[n] = 0; q.push(n); while(!q.empty()) { int u = q.front(); q.pop(); if(u != n) { int sz = rv[u].size(); { double ans = 0; for(auto v : rv[u]) { ans += dp1[v]; } dp1[u] = 1.0*(ans+sz+1)/sz; } { double ans = 0; for(auto v : rv[u]) { ans += dp2[v]; } dp2[u] = 1.0*(ans+1.0*(sz+1)*dp1[u])/sz; } } for(auto v : vv[u]) { ind[v]--; if(ind[v] == 0) q.push(v); } } } int main() { // freopen("in", "r", stdin); scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { vv[i].clear(); rv[i].clear(); dp1[i] = dp2[i] = 0; } for(int i=1, x, y; i<=m; i++) { scanf("%d%d", &x, &y); rv[x].pb(y); vv[y].pb(x); ind[x]++; } solve(); printf("%.2f\n", dp2[1]); } return 0; }

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/11494807.html