题目大意
给出一个 \(n\) 个点 \(m\) 条边的有向图,从 \(s\) 出发走到 \(t\) 的期望步数。
满足 \(n\le 10^4,m\le 10^6\) 且强连通分量大小 \(\le 100\)。
思路
不难看出 60 pts 做法,即直接高斯消元 \(n^3\)。
考虑 100 pts,我们发现如果我们缩了点,我们之后再拓扑排序,那么对于不在强连通分量内的一定已经求到,强连通内部的关系可以再高斯消元解决。
所以时间复杂度为 \(\Theta(10^4n+m)\)。
\(\texttt{Code}\)
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args& ... args){read (t),read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
stack <int> S;
bool vis[MAXN];
double f[MAXN],mat[205][205];
vector <int> G[MAXN],Su[MAXN],NG[MAXN];
int n,m,s,t,cnt,ind,tur[MAXN],Deg[MAXN],bel[MAXN],dfn[MAXN],low[MAXN];
void Tarjan (int u){
dfn[u] = low[u] = ++ ind,vis[u] = 1,S.push (u);
for (Int v : G[u]){
if (!dfn[v]) Tarjan (v),low[u] = min (low[u],low[v]);
else if (vis[v]) low[u] = min (low[u],dfn[v]);
}
if (low[u] == dfn[u]){
++ cnt;int v;
do vis[v = S.top()] = 0,bel[v] = cnt,Su[cnt].push_back (v),S.pop (); while (u ^ v);
}
}
void Solve (int u){
int siz = Su[u].size();
for (Int i = 1;i <= siz;++ i)
for (Int j = 1;j <= siz + 1;++ j) mat[i][j] = 0;
for (Int i = 1,now;i <= siz;++ i) now = Su[u][i - 1],tur[now] = i;
for (Int i = 1,now;i <= siz;++ i){
now = Su[u][i - 1];double p = 1.0 / Deg[now];
if (now == t){
mat[i][i] = 1,mat[i][siz + 1] = 0;
continue;
}
mat[i][i] = 1,mat[i][siz + 1] = 1;
for (Int v : G[now]) if (bel[v] ^ u) mat[i][siz + 1] += p * f[v];else mat[i][tur[v]] -= p;
}
for (Int i = 1;i <= siz;++ i){
int ind = i;
for (Int j = i + 1;j <= siz;++ j) if (abs (mat[j][i]) > abs (mat[ind][i])) ind = j;
if (!abs (mat[ind][i])) continue;
if (ind ^ i) swap (mat[i],mat[ind]);
for (Int j = i + 1;j <= siz;++ j){
double d = mat[j][i] / mat[i][i];
for (Int k = i;k <= siz + 1;++ k) mat[j][k] -= mat[i][k] * d;
}
}
for (Int i = siz;i >= 1;-- i){
for (Int j = i + 1;j <= siz;++ j) mat[i][siz + 1] -= f[Su[u][j - 1]] * mat[i][j];
f[Su[u][i - 1]] = mat[i][siz + 1] / mat[i][i];
}
}
void dfs (int u){
vis[u] = 1;
for (Int v : G[u]) if (!vis[v]) dfs (v);
}
signed main(){
read (n,m,s,t),srand (time(NULL));
for (Int i = 1,u,v;i <= m;++ i) read (u,v),G[u].push_back (v),Deg[u] ++;
dfs (s);if (!vis[t]) return puts ("INF"),0;
for (Int i = 1;i <= n;++ i) if (i != t && vis[i] && !Deg[i]) return puts ("INF"),0;
memset (vis,0,sizeof (vis));
for (Int i = 1;i <= n;++ i) if (!dfn[i]) Tarjan (i);
for (Int i = 1;i <= cnt;++ i) Solve (i);
if (f[s] > 1e10) puts ("INF");
else printf ("%.3f\n",f[s]);
return 0;
}