HDU 4418 Time travel（12年杭州 高斯消元求概率）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一个数轴，有一个起点和一个终点，某个人可以走1，2，3……m步，每一种情况有一个概率，初始有一个方向，走到头则返回，问到达终点的期望步数为多少。
http://acm.hdu.edu.cn/showproblem.php?pid=4418
比较明显的高斯求期望问题。
E[i]表示在i点的时候到达终点的期望步数，则E[i]=E[i+1]*p1+E[i+2]*p2+……E[i+m]*pm+1。
列好方向 ，高斯消元即可。
对于这种问题，注意无解情况，只需要先BFS一次，把有效的可行状态标号，即可
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#include<string>#include<queue>#define inf 1<<28#define M 6000005#define N 205#define maxn 300005#define eps 1e-8#define zero(a) fabs(a)<eps#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define lson step<<1#define rson step<<1|1using namespace std;int n,m,y,x,s,d,e;double p[N],a[N][N];int cnt,id[N],g[N];void debug(int n){ for(int i=0;i<n;i++){ for(int j=0;j<=n;j++) printf("%.2f ",a[i][j]); printf("\n"); }}bool bfs(){ queue<int>que; que.push(s); cnt=0;mem(id,-1); id[s]=cnt++; bool flag=false; while(!que.empty()){ int u=que.front();que.pop(); for(int i=1;i<=m;i++){ int v=(u+i)%(2*n-2); if(zero(p[i])) continue; if(id[v]!=-1) continue; id[v]=cnt++; if(g[v]==y) {flag=true;} que.push(v); } } return flag;}void Bulid(){ mem(a,0); for(int i=0;i<(2*n-2);i++){ if(id[i]==-1) continue; int u=id[i]; a[u][u]=1; if(g[i]==y){a[u][cnt]=0;continue;} for(int j=1;j<=m;j++){ int v=(i+j)%(2*n-2); if(id[v]==-1) continue; v=id[v]; a[u][v]-=p[j]; a[u][cnt]+=p[j]*j; } }}bool gauss(int n){ int i,j; for(i=0,j=0;i<n&&j<n;j++){ int k; for(k=i;k<n;k++) if(!zero(a[k][j])) break; if(k<n){ if(i!=k) for(int r=j;r<=n;r++) swap(a[i][r],a[k][r]); double tt=1/a[i][j]; for(int r=j;r<=n;r++) a[i][r]*=tt; for(int r=0;r<n;r++) if(r!=i){ for(int t=n;t>=j;t--) a[r][t]-=a[r][j]*a[i][t]; } i++; } } for(int r=i;r<n;r++) if(!zero(a[r][n])) return false; return true;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d%d%d%d",&n,&m,&y,&x,&d); for(int i=1;i<=m;i++){scanf("%lf",&p[i]);p[i]/=100.0;} if(x==y){printf("0.00\n");continue;} if(d==0)s=x; else if(d==1) s=n+(n-2-x); else s=x; for(int i=0;i<n;i++) g[i]=i; for(int i=n,j=n-2;j>=1;j--,i++) g[i]=j; if(!bfs()){puts("Impossible !");continue;} Bulid(); if(!gauss(cnt)) puts("Impossible !"); else{ for(int i=0;i<cnt;i++) if(zero(a[i][0]-1)){ double ans=a[i][cnt]; if(zero(ans)) printf("0.00\n"); else printf("%.2f\n",ans); break; } } } return 0;}