隐藏
「SDOI2012」走迷宫 - 期望动规+高斯消元 | Bill Yang's Blog
0%

「SDOI2012」走迷宫 - 期望动规+高斯消元

题目大意

    Morenan被困在了一个迷宫里。迷宫可以视为$N$个点$M$条边的有向图,其中Morenan处于起点$S$,迷宫的终点设为$T$。可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。


题目分析

很有意思的一道题。

首先如果题目中的图是一个DAG,显然可以做一个简单的期望转移。
然而题目的图可能是一个环。
环上每个点的期望互相关联,可以列出$c$个方程。(其中$c$是环上点数)
$c$个未知数$c$个方程,一定有唯一解,可以使用高斯消元求解。

若从$S$出发存在路径不能到达$T$,输出INF,因为无穷大不可能收敛下来。

第一次使用高斯约旦消元。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=10005;

int step=0,top=0,BCC=0,Dfn[maxn],Lowlink[maxn],Stack[maxn],Instack[maxn],Belong[maxn],Rank[maxn];
int n,m,s,t,vst[maxn],Degree[maxn];
vector<int> edges[maxn],edges2[maxn],Block[maxn];
map<int,map<int,int> > M;

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void AddEdge2(int x,int y) {
edges2[x].push_back(y);
}

void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int Next:edges[Now]) {
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
BCC++;
int y;
do {
y=Stack[top--];
Instack[y]=0;
Belong[y]=BCC;
Block[BCC].push_back(y);
Rank[y]=Block[BCC].size();
} while(y!=Now);
}
}

void Mark(int Now) {
vst[Now]=0;
if(Now==Belong[t]) {
vst[Now]=1;
return;
}
for(int Next:edges2[Now]) {
if(vst[Next]==-1)Mark(Next);
if(vst[Next]==1)vst[Now]=1;
}
}

const double eps=1e-6;
double a[205][205],f[maxn];

void Gauss_Jordan(int n) {
for(int i=1; i<=n; i++) {
int row=i;
for(; row<=n; row++)if(fabs(a[row][i])>eps)break;
if(row>n)continue;
for(int j=1; j<=n+1; j++)swap(a[i][j],a[row][j]);
double t=a[i][i];
for(int j=1; j<=n+1; j++)a[i][j]/=t;
for(int j=1; j<=n; j++)
if(j!=i) {
t=a[j][i];
for(int k=1; k<=n+1; k++)a[j][k]-=t*a[i][k];
}
}
}

void Solve(int Now) {
for(int Next:edges2[Now])if(!vst[Next])Solve(Next);
for(int i=1; i<=Block[Now].size(); i++)
for(int j=1; j<=Block[Now].size()+1; j++)a[i][j]=0;
for(int i=1; i<=Block[Now].size(); i++) {
a[i][i]=1;
int u=Block[Now][i-1];
if(u==t)continue;
a[i][Block[Now].size()+1]=1;
for(int v:edges[u]) {
if(Belong[v]==Now)a[i][Rank[v]]-=1.0/Degree[u];
else a[i][Block[Now].size()+1]+=1.0/Degree[u]*f[v];
}
}
Gauss_Jordan(Block[Now].size());
for(int u:Block[Now])f[u]=a[Rank[u]][Block[Now].size()+1];
vst[Now]=1;
}

int main() {
n=Get_Int();
m=Get_Int();
s=Get_Int();
t=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
Degree[x]++;
}
for(int i=1; i<=n; i++)
if(!Dfn[i])Tarjan(i);
for(int Now=1; Now<=n; Now++)
for(int Next:edges[Now]) {
if(Belong[Now]==Belong[Next]||(M.count(Belong[Now])&&M[Belong[Now]].count(Belong[Next])))continue;
M[Belong[Now]][Belong[Next]]=1;
AddEdge2(Belong[Now],Belong[Next]);
}
memset(vst,-1,sizeof(vst));
Mark(Belong[s]);
for(int i=1; i<=BCC; i++)
if(vst[i]==0) {
puts("INF");
return 0;
}
memset(vst,0,sizeof(vst));
Solve(Belong[s]);
printf("%0.3lf\n",f[s]);
return 0;
}
姥爷们赏瓶冰阔落吧~