欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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;
}