BZOJ2707: [SDOI2012]走迷宫(期望 tarjan 高斯消元)
程序员文章站
2022-07-09 20:47:07
题意 "题目链接" Sol 设$f[i]$表示从$i$走到$T$的期望步数 显然有$f[x] = \sum_{y} \frac{f[y]}{deg[x]} + 1$ 证明可以用全期望公式。 那么我们可以把每个强联通分量里的点一起高斯消元,就做完了。 (warning:BZOJ没有C++11,但是下面 ......
题意
sol
设\(f[i]\)表示从\(i\)走到\(t\)的期望步数
显然有\(f[x] = \sum_{y} \frac{f[y]}{deg[x]} + 1\)
证明可以用全期望公式。
那么我们可以把每个强联通分量里的点一起高斯消元,就做完了。
(warning:bzoj没有c++11,但是下面的代码是正确的,至于为什么可以点题目链接。。。。)
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 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, s, t; int dfn[maxn], low[maxn], vis[maxn], tot, cnt, inder[maxn], col[maxn], ha[maxn]; double f[201][201], deg[maxn], ans[maxn]; stack<int> s; vector<int> v[maxn], scc[maxn], e[maxn]; void pre() { for(int i = 1; i <= n; i++) { double sum = 0; f[i][i] = 1.0; for(auto &x : v[i]) if(x != t) sum += 1.0 / deg[x], f[i][x] = -1.0; f[i][n + 1] = sum; } } void gauss(int n) { for(int i = 1; i <= n; i++) { int mx = i; for(int j = i + 1; j <= n; j++) if(f[j][i] > f[mx][i]) mx = j; if(i != mx) swap(f[i], f[mx]); for(int j = 1; j <= n; j++) { if(i == j) continue; double p = f[j][i] / f[i][i]; for(int k = i + 1; k <= n + 1; k++) f[j][k] -= f[i][k] * p; } } for(int i = 1; i <= n; i++) f[i][n + 1] = f[i][n + 1] / f[i][i]; } void tarjan(int x) { dfn[x] = low[x] = ++tot; s.push(x); vis[x] = 1; for(auto &to : v[x]) { if(!dfn[to]) tarjan(to), low[x] = min(low[x], low[to]); else if(vis[to]) low[x] = min(low[x], dfn[to]); } if(low[x] == dfn[x]) { int h; cnt++; do { h = s.top(); s.pop(); vis[h] = 0; scc[cnt].push_back(h); col[h] = cnt; }while(h != x); } } void solve(vector<int> &p) { memset(vis, 0, sizeof(vis)); memset(f, 0, sizeof(f)); int num = p.size(); for(int i = 0; i < p.size(); i++) vis[p[i]] = i + 1; for(int i = 0; i < p.size(); i++) { int x = p[i]; f[i + 1][i + 1] = deg[x]; f[i + 1][num + 1] = deg[x]; for(auto &to : v[x]) { if(vis[to]) f[i + 1][vis[to]] -= 1; else f[i + 1][num + 1] += ans[to]; } } gauss(num); for(int i = 0; i < p.size(); i++) ans[p[i]] = f[i + 1][num + 1]; } void topsort() { queue<int> q; q.push(col[t]); while(!q.empty()) { int p = q.front(); q.pop(); for(auto &to : e[p]) if(!(--inder[to])) q.push(to); if(p != col[t]) solve(scc[p]); } } int main() { n = read(); m = read(); s = read(); t = read(); for(int i = 1; i <= m; i++) { int x = read(), y = read(); if(x != t) v[x].push_back(y), deg[x]++; } tarjan(s); if(!dfn[t]) {puts("inf"); return 0;} for(int i = 1; i <= n; i++) { for(auto &x : v[i]) if(col[i] != col[x]) inder[col[i]]++, e[col[x]].push_back(col[i]); } for(int i = 1; i <= cnt; i++) if(i != col[t] && !inder[i]) {puts("inf"); return 0;} topsort(); printf("%.3lf", ans[s]); return 0; }