自动搬运

查看原文

来自洛谷，原作者为

	tzc_wk **

搬运于2025-08-24 22:16:41，当前版本为作者最后更新于2021-04-04 01:30:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门

之所以写个题解是因为题解区大部分题解的做法都有 bug（u1s1 周六上午在讨论区里连发两个 hack 的是我，由于我被禁言才让 ycx 代发的）

首先碰到这种期望题，我们套路地设 $dp_u$ 为从节点 $u$ 走到节点 $n$ 经过的节点数的期望值，那么显然有转移方程 $dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1$，由于这个 $dp$ 方程存在环，故需按照 P3232 游走 的套路进行高斯消元，具体来说你将这 $n$ 个 $dp$ 转移式写成矩阵的形式高斯消元一下即可。

等等……$10^4$ 你让我跑高斯消元？

注意到题目中有个条件，就是每个强连通分量大小 $\le 100$，因此考虑先将原图进行一遍 SCC 缩点，缩点完成后显然原图变成了一个 DAG，我们考虑按这个 DAG 的拓扑序倒序（或者说，以 $t$ 为起点拓扑排序）对每个强连通分量中的点计算一遍 $dp$ 值，具体来说我们给当前强连通分量中的所有点重新编号，对于形如 $dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1$ 的式子，如果 $v$ 与 $u$ 在同一个强连通分量中那就按照套路将式子改写成一个 $dp_u$ 与这样的 $dp_v$ 的关系式，否则由于我们按照拓扑序倒序计算答案，$dp_v$ 的值肯定已经计算好了，那么我们把它当作常数项拖到右边去即可。具体实现的时候可以以 $s$ 为起点跑一遍 tarjan，因为最终强连通分量的编号本身就是按拓扑序倒序编好号的了，就 duck 不必再写遍拓扑排序了，直接从 $1$ 枚举到 $\text{强连通分量个数}$ 依次计算即可。

记 $s_i$ 为强连通分量大小，那么该算法复杂度 $T(n)=\sum\limits_{i=1}^ms_i^3$，而 $s_i\le 100$，故 $T(n)\le\dfrac{10^4}{100}\times 100^3=10^8$，可以通过此题。

那么什么情况输出 INF 呢？显然如果 $s$ 不能到 $t$ 答案肯定是 INF，接下来就是我要强调的地方了，不少题解都认为，只要存在 $s$ 能到达但却不能到达 $t$ 的点就 INF，但考虑下面的数据：

3 2 1 3
1 3
3 2

事实上，$2$ 虽然能够从 $3$ 到达，但从 $1\to 2$ 的路径上已经经过 $3$ 了，因此是可以到达 $2$ 的，答案应当为 $1.000$。

还有的题解稍微明智些，把不能到达的点的 $dp$ 值设为 $\infty$，然后判是否有 $dp_s=\infty$，这样做是可以避免掉上述情况的，但由于实现上出了个小 bug（如果一个点出度为 $0$ 那么它的 $dp$ 值就是 $\infty$），导致其可以被以下的数据叉掉：

5 5 1 5
1 5
1 2
2 3
3 4
4 2

我的做法是，先建反图，以 $t$ 为起点做一遍 DFS 找出所有能到达 $t$ 的点，然后如果一个点不能到达 $t$ 那就令它的 $dp$ 值为 $\infty$，这样又可避免上述情况。

当然我的做法可能也存在漏洞（只是我发现不了了），如果发现漏洞请及时提出，谢谢。

我认为做题还是要严谨些，愿管理员把 hack 数据加入本题的测试数据中。

那问题就来了，为什么我就不能把我 hack 的这份热情放到 CF 比赛中呢

const int MAXS=100;
const int MAXN=10000;
const int MAXM=1e6;
const double INF=1e15;
int n,m,s,t;
int hd[MAXN+5],to[MAXM*2+5],nxt[MAXM*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int bel[MAXN+5],cmp=0,dfn[MAXN+5],low[MAXN+5],tim=0;
bool vis[MAXN+5];int stk[MAXN+5],top=0;vector<int> scc[MAXN+5];
vector<int> rev[MAXN+5];bool can[MAXN+5];
void dfs(int x){
	if(can[x]) return;can[x]=1;
	for(int y:rev[x]) dfs(y);
}
void tarjan(int x){
	dfn[x]=low[x]=++tim;vis[x]=1;stk[++top]=x;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];
		if(!dfn[y]) tarjan(y),chkmin(low[x],low[y]);
		else if(vis[y]) chkmin(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		cmp++;int o;
		do {
			o=stk[top--];vis[o]=0;
			scc[bel[o]=cmp].pb(o);
		} while(o!=x);
	}
}
int id[MAXN+5],seq[MAXS+5],subsiz=0,deg[MAXN+5];
double dp[MAXN+5],a[MAXS+5][MAXS+5],f[MAXS+5];
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);deg[u]++;
		adde(u,v);rev[v].pb(u);
	}
	tarjan(s);dfs(t);if(!dfn[t]) return puts("INF"),0;
	for(int i=1;i<=cmp;i++){
		subsiz=0;memset(a,0,sizeof(a));memset(f,0,sizeof(f));
		for(int u:scc[i]){seq[++subsiz]=u;id[u]=subsiz;}
		for(int u:scc[i]){
			int p=id[u];
			if(u==t){a[p][p]=1;continue;}
			a[p][p]=a[p][subsiz+1]=deg[u];
			for(int e=hd[u];e;e=nxt[e]){
				int v=to[e];
				if(bel[v]==bel[u]) a[p][id[v]]--;
				else a[p][subsiz+1]+=dp[v];
			}
			if(!can[u]) a[p][subsiz+1]=INF;
		}
//		for(int j=1;j<=subsiz;j++) for(int k=1;k<=subsiz+1;k++)
//			printf("%.3lf%c",a[j][k],(k==subsiz+1)?'\n':' ');
		for(int j=1;j<=subsiz;j++){
			int t=j;
			for(int k=j+1;k<=subsiz;k++) if(fabs(a[k][j])>fabs(a[t][j])) t=k;
			for(int k=j;k<=subsiz+1;k++) swap(a[t][k],a[j][k]);
			for(int k=j+1;k<=subsiz+1;k++) a[j][k]/=a[j][j];a[j][j]=1;
			for(int k=j+1;k<=subsiz;k++){
				for(int l=j+1;l<=subsiz+1;l++) a[k][l]-=a[k][j]*a[j][l];
				a[k][j]=0;
			}
		}
		for(int j=subsiz;j;j--){
			f[j]=a[j][subsiz+1];
			for(int k=j+1;k<=subsiz;k++) f[j]-=f[k]*a[j][k];
//			printf("%.3lf\n",f[j]);
		}
		for(int j=1;j<=subsiz;j++){
			if(f[j]>1e9) dp[seq[j]]=INF;
			else dp[seq[j]]=f[j];
		}
	}
//	for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
	if(dp[s]>1e9) puts("INF");
	else printf("%.3lf\n",dp[s]);
	return 0;
}