Luogu6030 SDOI2012 走迷宫

Description

link

给定一个有向图，求从 (S) 走到 (T) 的期望步数

如果没法走到(T)，那么步数为 (inf)

求期望步数

(nle 10^4) 每个强连通分量的大小不超过 (100)

Solution

有向图，期望

(tarjan) 和高斯消元呗

我们先列个式子

[f_i=1+frac{1}{d_i}sum_{(i,j)in E} f_j ]

其中 (f_i) 表示从 (i) 到 (T) 的期望步数

我们发现这个直接上高斯消元是不大行的

然后题目中：

“每个强连通分量的大小不超过 (100) ”

所以我们想到了对于每个强连通分量里面消元

这样大概是个 (O(100^4)) 的复杂度，还跑不满

考虑到 (tarjan) 出栈的有序性，我们从 (1) 到 (n) 进行消元就 (Ok) 了

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar(); 
		return res*f;
	}
	const int N=1e4+10;
	vector<int> g[N],scc[N];
	int n,m,s,t;
	int dfn[N],low[N],tim,st[N],top,vis[N],d[N],p[N],cnt,id[N];
	double a[200][200],ans[N],f[N];
	inline void tarjan(int x)
	{
		dfn[x]=low[x]=++tim; st[++top]=x; vis[x]=1;
		int sz=g[x].size();
		for(int i=0;i<sz;++i)
		{
			int t=g[x][i];
			if(!dfn[t]) tarjan(t),low[x]=min(low[x],low[t]);
			else if(vis[t]) low[x]=min(low[x],dfn[t]);
		}
		if(low[x]==dfn[x])
		{
			cnt++;
			do{
				id[st[top]]=cnt; 
				vis[st[top]]=0; 
				scc[cnt].push_back(st[top]);
				p[st[top]]=scc[cnt].size();
				top--;
			}while(st[top+1]!=x);
		} return ;
	}
	
	inline void guass(int x)
	{
		for(int i=1;i<=x;++i) 
		{
			int t=i;
			for(int j=i+1;j<=x;++j) if(fabs(a[j][i])>fabs(a[t][i])) t=j; 
			if(i!=t) swap(a[i],a[t]);
			if(fabs(a[i][i])==0) return ;
			for(int j=i+1;j<=x;++j)
			{
				double d=a[j][i]/a[i][i]; 
				for(int k=1;k<=x+1;++k) a[j][k]-=a[i][k]*d;
			} 
		}
		for(int i=x;i>=1;--i)
		{
			for(int j=i+1;j<=x;++j) a[i][x+1]-=ans[j]*a[i][j];
			ans[i]=a[i][x+1]/a[i][i];
		}
		return ;
	}
	signed main()
	{
		n=read(); m=read(); s=read(); t=read();
		for(int i=1;i<=m;++i)
		{
			int x=read(),y=read(); d[x]++;
			g[x].push_back(y); 
		}
		tarjan(s); if(!dfn[t]) return puts("INF"),0;
		for(int i=1;i<=cnt;++i)
		{
			memset(a,0,sizeof(a)); 
			memset(ans,0,sizeof(ans));
			int sz=scc[i].size();
			for(int j=0;j<sz;++j)
			{
				int now=scc[i][j];
				if(now==t){a[p[now]][p[now]]=1; continue;}
				a[p[now]][p[now]]=1; a[p[now]][sz+1]=1;
				int siz=g[now].size(); 
				for(int k=0;k<siz;++k)
				{
					int t=g[now][k];
					if(id[t]==id[now]) a[p[now]][p[t]]-=1.0/d[now];
					else a[p[now]][sz+1]+=f[t]/d[now];
				}
				if(!siz) a[p[now]][sz+1]=1e18;
			}
			guass(sz);
			for(int j=0;j<sz;++j)
			{
				f[scc[i][j]]=ans[p[scc[i][j]]]; 
				if(f[scc[i][j]]>1e10) f[scc[i][j]]=1e18;
			}
		}
		if(f[s]>1e10) puts("INF");
		else printf("%.3lf
",f[s]);
		return 0;
	}
}
signed main(){return yspm::main();}

Review

面向数据范围编程.jpg

还有，如果明确高斯消元了，而且复杂度太大，那就根据题里的信息降复杂度