bzoj 2707: [SDOI2012]走迷宫 （高斯消元+概率期望+tarjan缩点+拓扑序）

Description

Input

Output

Sample Input

Sample Output

HINT

Source

round 1 day1

题解：高斯消元+概率期望+tarjan缩点+拓扑序

首先感谢zyf2000神犇在我做题的过程中解决我的各种傻逼问题。。。。

对于这道题来说，我们一定要理解清楚题意。题中说的到不了终点不是单纯的说起点和终点不连通，而是说如果有一条路无论如何都到不了终点，那么在走的过程中如果选择了这条路，那么这条路的期望就是INF，对于总的答案来说也是INF。所以我们在缩点之后形成的有向无环图中，如果出度为0的点不只belong[t]或者不是belong[t]，那么对于期望步数来书就是INF。

首先进行tarjan缩点，然后按照拓扑序的倒序进行计算。另E[t]=0，然后向前推。

E[x]=(E[v[i]]+1)*p[out[x]] 其中p表示选择走这条边的概率

对于一个强联通分量中的点，建立方程组，然后用高斯消元求解。把强联通分量中的点的E当成未知量，之外的已经求得的点当做常量求解即可。

注意细节，想明白了应该不算太难写。刚开始想的有问题，当时感觉真是难写。

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#define N 203#define M 2000003#define P 10003#define eps 1e-9using namespace std;double a[N][N],b[N],ans[N],E[P];int n,m,s,t,out[P],ck[P],vi[P];int point[M],nxt[M],v[M],tot,dfsn[P],low[P],ins[P],top,sz,cnt,belong[P],st[P];int head[M],next[M],u[M],mp[P],xk[M],yk[M],du[P];void guass(int n){	for (int i=1;i<=n;i++) {		int num=i;		for (int j=i+1;j<=n;j++)		 if (fabs(a[j][i])>fabs(a[num][i])) num=j;		if (num!=i) {		 for (int j=1;j<=n;j++) swap(a[num][j],a[i][j]);		 swap(b[num],b[i]);	    }	    for (int j=i+1;j<=n;j++) {	    	if (fabs(a[j][i])<eps) continue;	    	double t=a[j][i]/a[i][i];	    	for (int k=1;k<=n;k++)	    	 a[j][k]-=a[i][k]*t;	    	b[j]-=b[i]*t;		}	}	for (int i=n;i>=1;i--) {		double t=1.0*b[i];		if (fabs(a[i][i])<eps) continue;		for (int j=i+1;j<=n;j++) t-=ans[j]*a[i][j];		ans[i]=t/a[i][i];	}}struct data{	int x[103],cnt;	void solve()	{		memset(b,0,sizeof(b));		memset(a,0,sizeof(a));		for (int i=1;i<=cnt;i++) {			if (x[i]==t) {				b[i]=0;				a[i][i]=1;				continue;			}			double p=1.0/out[x[i]];			a[i][i]=1;			for (int j=point[x[i]];j;j=nxt[j]){				if (E[v[j]]!=-1) b[i]+=p*(E[v[j]]+1.0);				else a[i][mp[v[j]]]-=p,b[i]+=p;			}		}		guass(cnt);		for (int i=1;i<=cnt;i++)		 E[x[i]]=ans[i];	}}T[10003];void add(int x,int y){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void tarjan(int x){    ins[x]=1; st[++top]=x; low[x]=dfsn[x]=++sz;    for (int i=point[x];i;i=nxt[i]) {    	int j=v[i];    	if (!dfsn[j]) tarjan(j),low[x]=min(low[x],low[j]);    	else if (ins[j]) low[x]=min(low[x],dfsn[j]);	}	if (low[x]==dfsn[x]) {		++cnt;		int j;		do {			j=st[top--];			belong[j]=cnt;			ins[j]=0;		}while (j!=x);	}}void build(int x,int y){   	tot++; next[tot]=head[x]; head[x]=tot; u[tot]=y;}int main(){	freopen("input.in","r",stdin);	scanf("%d%d%d%d",&n,&m,&s,&t);	for (int i=1;i<=m;i++) {		int x,y; scanf("%d%d",&x,&y);		add(x,y); out[x]++; ins[y]++;	}	for (int i=1;i<=n;i++)	 if (!ins[i]&&!out[i]) ck[i]=1;	memset(ins,0,sizeof(ins));	for (int i=1;i<=n;i++)	 if (!dfsn[i]) tarjan(i);	for (int i=1;i<=n;i++) {		int t=belong[i];		T[t].x[++T[t].cnt]=i;		mp[i]=T[t].cnt;	}	tot=0;	for (int i=1;i<=n;i++) 	 for (int j=point[i];j;j=nxt[j]) {	 	int r1=belong[i]; int r2=belong[v[j]];	 	if (r1!=r2) build(r2,r1),du[r1]++;	 }	for (int i=1;i<=n;i++) 	 if(ck[i]) vi[belong[i]]=1;	int num=0; int pos=0;	for (int i=1;i<=cnt;i++)	 if (du[i]==0&&!vi[i]) num++,pos=i;	if (num>1||num==1&&pos!=belong[t]) {		PRintf("INF/n");		return 0;	}	queue<int> p; p.push(pos);	for (int i=1;i<=n;i++) E[i]=-1;	while (!p.empty()) {		int now=p.front(); p.pop();		T[now].solve();		for (int i=head[now];i;i=next[i]) {			du[u[i]]--;			if (!du[u[i]]) p.push(u[i]);		}	}	if (E[s]==-1||m==0) printf("INF/n"); 	else printf("%.3lf/n",E[s]);}