C++14(g++5.4) 解法, 执行用时: 377ms, 内存消耗: 20672K, 提交时间: 2019-11-28 15:06:12

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define f80 long double
#define rgt register
#define fp( i, b, e ) for ( rgt int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( rgt int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline bool cmax( T &x, T y ){ return x < y ? x = y, 1 : 0; }
template<typename T> inline bool cmin( T &x, T y ){ return y < x ? x = y, 1 : 0; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
	for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
	for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
	flg ? x = -x : x;
}

const int _ = 1e4 + 15, __ = 1e6 + 15;
int N, M, S, T, d[_], h[_];
int hd[_], nxt[__], to[__], tot;
int dfn[_], low[_], s[_], c[_], tp, num, cnt;
vector<int> vec[_];
double a[105][105], f[_];

inline void addedge( int x, int y ){
	nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y;
}


void Tarjan( int u ){
	dfn[u] = low[u] = ++num, s[++tp] = u;
	go( i, hd[u] ) if ( !dfn[v] ) Tarjan(v), cmin( low[u], low[v] );
	else if ( !c[v] ) cmin( low[u], dfn[v] );
	if ( dfn[u] == low[u] ){ ++cnt; while( s[tp + 1] != u ) c[s[tp--]] = cnt; }
}

void Gauss( int n ){
	fp( i, 1, n ){
		int o(-1); fp( j, i, n ) if ( abs(a[j][i]) > 1e-10 ){ o = j; break; }
		if ( o == -1 ){ printf("INF\n"); exit(0); }
		if ( o != i ) fp( j, i, n ) swap( a[i][j], a[o][j] );
		double t(a[i][i]); fp( j, i, n + 1 ) a[i][j] /= t;
		fp( j, 1, n ) if ( i != j ){ t = a[j][i]; fp( k, i, n + 1 ) a[j][k] -= t * a[i][k]; }
	}
}

void work( int w ){
	int n = vec[w].size(); memset( a, 0, sizeof a );
	fp( i, 1, n ) h[vec[w][i - 1]] = i;
	fp( i, 1, n ){
		int u(vec[w][i - 1]); a[i][n + 1] += 1 + f[u], a[i][i] += 1;
		go( j, hd[u] ) if ( c[v] == w ) if ( c[v] == w ) a[h[v]][h[u]] -= 1. / d[v];
	} Gauss(n); fp( i, 1, n ) f[vec[w][i - 1]] = a[i][n + 1];
	for ( int u : vec[w] ) go( i, hd[u] ) if ( c[v] != w ) f[v] += f[u] / d[v];
}

bool vis[_];
bool check( int u ){
	if ( u == S ) return 1;
	vis[u] = 1; go( i, hd[u] ) if ( !vis[v] && check(v) ) return 1;
	return 0;
}

signed main(){
	read(N), read(M), read(S), read(T);
	int x, y; fp( i, 1, M ) read(x), read(y), x != T ? addedge(y, x), ++d[x] : 1;
	Tarjan(T); if ( !dfn[S] ) return printf("INF\n"), 0;
	fp( i, 1, N ) if ( !c[i] && check(i) ) return printf("INF\n"), 0;
	fp( i, 1, N ) vec[c[i]].push_back(i); fd( i, cnt - 1, 1 ) work(i);
	printf( "%.3lf\n", f[S] );
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 309ms, 内存消耗: 7432K, 提交时间: 2020-04-15 22:28:56

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int N=1e4+5,M=1e6+5;
vector<int>g[N];
int n,m,s,t;
int du[N];
double a[105][105],f[N];
vector<int>b[N];
int dfn[N],low[N],col,co[N],num;
int stk[N],tp;
void tarjan(int u){
    dfn[u]=low[u]=++num;stk[++tp]=u;
    for(auto v:g[u])if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
    else if(!co[v])low[u]=min(low[u],dfn[v]);
    if(dfn[u]==low[u]){++col;while(stk[tp+1]!=u)co[stk[tp--]]=col;}
}
bool vis[N];
bool check(int x){
    if(x==s)return 1;
    vis[x]=1;
    for(auto v:g[x])if(!vis[v]&&check(v))return 1;
    return 0;
}
void gauss(int n){
    for(int i=1;i<=n;i++){
        int t=i;
        for(int j=i+1;j<=n;j++)if(fabs(a[j][i]>fabs(a[t][i])))t=j;
        swap(a[t],a[i]);
        if(fabs(a[i][i])<eps){puts("INF");exit(0);}
        for(int j=1;j<=n;j++)if(j!=i){
            double x=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++)a[j][k]-=x*a[i][k];
        }
    }
    for(int i=1;i<=n;i++)a[i][n+1]/=a[i][i];
}
int h[N];
void solve(int x){
    int n=b[x].size();memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)h[b[x][i-1]]=i;
    for(int i=1;i<=n;i++){
        int u(b[x][i-1]);a[i][n+1]+=1+f[u];a[i][i]+=1;
        for(auto v:g[u])if(co[v]==x)a[h[v]][i]-=1./du[v];
    }
    gauss(n);for(int i=1;i<=n;i++)f[b[x][i-1]]=a[i][n+1];
    for(auto u:b[x])for(auto v:g[u])if(co[v]!=x)f[v]+=f[u]/du[v];
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
       // cin>>u>>v;
        if(u!=t)g[v].push_back(u),du[u]++;
    }
    tarjan(t);
    if(!dfn[s]){puts("INF");return 0;}
    for(int i=1;i<=n;i++)if(!dfn[i]&&check(i)){puts("INF");return 0;}
    for(int i=1;i<=n;i++)b[co[i]].push_back(i);
    for(int i=col-1;i;i--)solve(i);
    printf("%.3lf\n",f[s]);
    return 0;
}