问题分析
数据范围唬人的……毕竟 (|Scc|leqslant 100) 。难写点罢了。
令 (f_i) 表示 (i) 到 (T) 的期望步数，那么有 (f_i=1+frac{1}{Deg_i}sumlimits_{(i,v)in E}f_v) 。
那么只要一个 (Scc) 内高斯消元， (Scc) 之间按反着的拓扑序做即可。
不好好学tarjan又被教育了
参考程序
我也不知道为什么要写得这么翔
#include <cstdio>
#include <vector>
#include <cstring>
//#define __DEBUG__
#define Maxn 10010
#define Maxm 1000010
#define MaxScc 110
struct edge {
int To, Next;
edge() {}
edge(int _To, int _Next) : To(_To), Next(_Next) {}
};
edge Edge[Maxm];
int Start[Maxn], UsedEdge;
int n, m, s, t, P[Maxn], Ref[Maxn];
int Dfn[Maxn], Low[Maxn], Time, Vis[Maxn];
int Stack[Maxn];
edge rEdge[Maxm];
int rStart[Maxn], rUsedEdge;
std::vector<int> Scc[Maxn];
int SccNum[Maxn];
int Index[Maxn], Degree[Maxn];
int L, R, Queue[Maxn];
long double Ans[Maxn];
long double A[MaxScc][MaxScc];
inline void AddEdge(int x, int y);
inline void rAddEdge(int x, int y);
void Dfs(int u);
inline void GetScc(int t);
inline void Go();
inline void Build(int u);
inline void Gauss(int n);
inline void Pan(int u);
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
if (u != t) {
AddEdge(v, u);
rAddEdge(u, v);
++P[u];
}
}
GetScc(t);
if (Dfn[s] == 0) {
printf("INF
");
return 0;
}
Pan(s);
for (int i = 1; i <= n; ++i)
if (Vis[i] && !Dfn[i]) {
printf("INF
");
return 0;
}
memset(Vis, 0, sizeof(Vis));
Go();
printf("%.3Lf
", Ans[s]);
#ifdef __DEBUG__
for (int i = 1; i <= n; ++i) printf("%.3Lf
", Ans[i]);
#endif
return 0;
}
inline void AddEdge(int x, int y) {
Edge[++UsedEdge] = edge(y, Start[x]);
Start[x] = UsedEdge;
return;
}
inline void rAddEdge(int x, int y) {
rEdge[++rUsedEdge] = edge(y, rStart[x]);
rStart[x] = rUsedEdge;
return;
}
inline void GetScc(int t) {
Dfs(t);
#ifdef __DEBUG__
printf("Num = %d
", SccNum[0]);
for (int i = 1; i <= SccNum[0]; ++i) {
printf(" %d : ", i);
for (int j = 0; j < SccNum[i]; ++j)
printf(" %d", Scc[i][j]);
printf("
");
}
#endif
for (int i = 1; i <= SccNum[0]; ++i)
for (int j = 0; j < SccNum[i]; ++j)
Index[Scc[i][j]] = i;
for (int u = 1; u <= n; ++u)
for (int t = Start[u]; t; t = Edge[t].Next) {
int v = Edge[t].To;
if (Index[u] != Index[v])
++Degree[Index[v]];
}
L = R = 0;
for (int i = 1; i <= SccNum[0]; ++i)
if (Degree[i] == 0)
Queue[++R] = i;
return;
}
void Dfs(int u) {
Dfn[u] = Low[u] = ++Time;
Vis[u] = 1;
Stack[++Stack[0]] = u;
for (int t = Start[u]; t; t = Edge[t].Next) {
int v = Edge[t].To;
if (!Dfn[v]) Dfs(v), Low[u] = std::min(Low[v], Low[u]);
else if (Vis[v]) Low[u] = std::min(Low[u], Low[v]);
}
if (Low[u] != Dfn[u]) return;
++SccNum[0];
while (Stack[Stack[0]] != u) {
Vis[Stack[Stack[0]]] = 0;
Scc[SccNum[0]].push_back(Stack[Stack[0]--]);
}
Vis[Stack[Stack[0]]] = 0;
Scc[SccNum[0]].push_back(Stack[Stack[0]--]);
SccNum[SccNum[0]] = Scc[SccNum[0]].size();
return;
}
inline void Go() {
while (L < R) {
int u = Queue[++L];
Build(u);
Gauss(SccNum[u]);
#ifdef __DEBUG__
printf(">>>>>>>>>> Scc %d <<<<<<<<<<
", u);
#endif
for (int i = 0; i < SccNum[u]; ++i) {
Ans[Scc[u][i]] = A[i + 1][SccNum[u] + 1];
for (int t = Start[Scc[u][i]]; t; t = Edge[t].Next) {
int v = Index[Edge[t].To];
if (v != u) {
--Degree[v];
if (Degree[v] == 0) Queue[++R] = v;
}
}
}
Ans[t] = 0;
}
return;
}
inline void Build(int S) {
memset(A, 0, sizeof(A));
for (int i = 0; i < SccNum[S]; ++i) Ref[Scc[S][i]] = i + 1;
for (int i = 0; i < SccNum[S]; ++i) {
A[i + 1][i + 1] = A[i + 1][SccNum[S] + 1] = 1;
int u = Scc[S][i];
for (int t = rStart[u]; t; t = rEdge[t].Next) {
int v = rEdge[t].To;
if (Index[v] == S) A[i + 1][Ref[v]] += -1.0 / P[u];
else A[i + 1][SccNum[S] + 1] += Ans[v] / P[u];
}
}
#ifdef __DEBUG__
printf("========== Part ===========
");
for (int i = 0; i < SccNum[S]; ++i) printf("%d ", Scc[S][i]); printf("
");
for (int i = 1; i <= SccNum[S]; ++i) {
for (int j = 1; j <= SccNum[S] + 1; ++j)
printf("%6.3Lf ", A[i][j]);
printf("
");
}
#endif
return;
}
inline void Gauss(int n) {
for (int i = 1; i <= n; ++i) {
long double Tmp = A[i][i];
for (int j = 1; j <= n + 1; ++j) A[i][j] /= Tmp;
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
Tmp = A[j][i];
for (int k = 1; k <= n + 1; ++k) A[j][k] -= A[i][k] * Tmp;
}
}
return;
}
inline void Pan(int u) {
Vis[u] = 1;
for (int t = rStart[u]; t; t = rEdge[t].Next) {
int v = rEdge[t].To;
if (Vis[v]) continue;
Pan(v);
}
return;
}