BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )

数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了.

E(u) = 1 + Σ E(v) / degree(u)

对拍时发现网上2个程序的INF判断和我不一样(他们2个的INF判断也不一样).....然而都A掉了....我觉得应该是他们写错了，我的做法应该没错的(正反2遍dfs,GDOI2015day1t1大冒险)(求打脸

------------------------------------------------------------------------

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 10009;

const int maxb = 209;

const double eps = 1e-8;

int N, S, T, deg[maxn];

int dfn[maxn], low[maxn], sz[maxn], CK;

int scc[maxn], Scc[maxn][maxb], Id[maxn], n;

bool F[maxn];

stack<int> stk;

double ans[maxn], mat[maxb][maxb];

inline void Min(int &x, int t) {

if(t < x) x = t;

}

struct edge {

int t;

edge* n;

} E[5000000], *pt = E;

struct G {

edge* H[maxn];

bool vis[maxn];

inline void AddEdge(int u, int v) {

pt->t = v, pt->n = H[u], H[u] = pt++;

}

void dfs(int x) {

vis[x] = true;

for(edge* e = H[x]; e; e = e->n)

if(!vis[e->t]) dfs(e->t);

}

void DFS(int x) {

memset(vis, 0, sizeof vis);

dfs(x);

}

} g[3];

void tarjan(int x) {

dfn[x] = low[x] = ++CK;

stk.push(x);

for(edge* e = g[0].H[x]; e; e = e->n) if(!dfn[e->t]) {

tarjan(e->t);

Min(low[x], low[e->t]);

} else if(!~scc[e->t])

Min(low[x], dfn[e->t]);

if(dfn[x] == low[x]) {

int t;

do {

t = stk.top(); stk.pop();

scc[t] = n;

Id[t] = sz[n];

Scc[n][sz[n]++] = t;

} while(t != x);

n++;

}

void Init() {

int m, u, v;

scanf("%d%d%d%d", &N, &m, &S, &T);

S--, T--;

memset(deg, 0, sizeof deg);

while(m--) {

scanf("%d%d", &u, &v);

u--, v--;

if(u == T) continue;

g[0].AddEdge(u, v);

deg[u]++;

}

void Solve(int x) {

if(x == scc[T]) {

ans[T] = 0;

return;

}

for(int i = 0; i < sz[x]; i++) {

for(int j = 0; j < sz[x]; j++) mat[i][j] = 0;

mat[i][sz[x]] = deg[Scc[x][i]];

for(edge* e = g[0].H[Scc[x][i]]; e; e = e->n)

if(scc[e->t] == x) {

mat[i][Id[e->t]]--;

} else if(e->t != T)

mat[i][sz[x]] += ans[e->t];

mat[i][i] += deg[Scc[x][i]];

}

for(int i = 0, r; i < sz[x]; i++) {

r = i;

for(int j = i; ++j < sz[x]; )

if(fabs(mat[j][i]) > fabs(mat[r][i])) r = j;

if(r != i) {

for(int j = 0; j <= sz[x]; j++)

swap(mat[i][j], mat[r][j]);

}

for(int j = i; ++j < sz[x]; ) {

double t = mat[j][i] / mat[i][i];

for(int k = i; k <= sz[x]; k++)

mat[j][k] -= t * mat[i][k];

}

for(int i = sz[x]; i--; ) {

for(int j = i; ++j < sz[x]; )

mat[i][sz[x]] -= mat[j][sz[x]] * mat[i][j];

mat[i][sz[x]] /= mat[i][i];

}

for(int i = 0; i < sz[x]; i++)

ans[Scc[x][i]] = mat[i][sz[x]];

}

void dfs(int x) {

for(edge* e = g[1].H[x]; e; e = e->n)

if(!F[e->t]) dfs(e->t);

F[x] = true;

Solve(x);

}

void Work() {

if(S == T) {

puts("0.000");

return;

}

memset(dfn, 0, sizeof dfn);

memset(scc, -1, sizeof scc);

memset(sz, 0, sizeof sz);

CK = n = 0;

for(int i = 0; i < N; i++)

if(!dfn[i]) tarjan(i);

for(int i = 0; i < N; i++)

for(edge* e = g[0].H[i]; e; e = e->n) if(scc[i] != scc[e->t]) {

g[1].AddEdge(scc[i], scc[e->t]);

g[2].AddEdge(scc[e->t], scc[i]);

}

g[1].DFS(scc[S]), g[2].DFS(scc[T]);

for(int i = 0; i < n; i++) if(g[1].vis[i] && !g[2].vis[i]) {

puts("INF"); return;

}

memset(F, 0, sizeof F);

dfs(scc[S]);

printf("%.3lf ", ans[S]);

}

int main() {

Init();

Work();

return 0;

}

------------------------------------------------------------------------

2707: [SDOI2012]走迷宫

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 372 Solved: 149
[Submit][Status][Discuss]

Description

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

Input

第1行4个整数，N,M,S,T

第[2, M+1]行每行两个整数o1, o2，表示有一条从o1到o2的边。

Output

一个浮点数，保留小数点3位，为步数的期望值。若期望值为无穷大，则输出"INF"。

【样例输入1】

6 6 1 6

1 2

1 3

2 4

3 5

4 6

5 6

【样例输出1】

3.000

【样例输入2】

9 12 1 9

1 2

2 3

3 1

3 4

3 7

4 5

5 6

6 4

6 7

7 8

8 9

9 7

【样例输出2】

9.500

【样例输入3】

2 0 1 2

【样例输出3】

INF

【数据范围】

测试点	N	M	Hint
[1, 6]	<=10	<=100
[7, 12]	<=200	<=10000
[13, 20]	<=10000	<=1000000	保证强连通分量的大小不超过100