首页 > 代码库 > hdu-4418-Time travel-高斯+概率dp
hdu-4418-Time travel-高斯+概率dp
把N个点先转化为2*N-2个点。
比如说把012345转化成0123454321。
这样,就可以找出任意两两个点之间的关系。
然后根据关系可以得出来一个一元多项式的矩阵。
然后就用高斯消元求出矩阵即可。
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<queue> #include<math.h> using namespace std; #define eps 1e-6 #define zero(x) ((fabs(x)<eps?0:x)) #define maxn 220 double a[maxn][maxn]; int g[maxn],cnt; int n,m,st,ed; double p[maxn]; int guss(int n) { int r; for(int i=0;i<n;i++) { r=i; for(int j=i+1;j<n;j++) { if(fabs(a[j][i])>fabs(a[r][i]))r=j; } if(!zero(a[r][i]))return 0; if(r!=i){ for(int j=0;j<=n;j++) swap(a[i][j],a[r][j]); } for(int j=i+1;j<=n;j++)a[i][j]/=a[i][i]; a[i][i]=1.0; for(int j=0;j<n;j++) { if(j==i)continue; for(int k=i+1;k<=n;k++) { a[j][k]-=a[i][k]*a[j][i]; } a[j][i]=0; } } return 1; } void bfs() { queue<int>que; while(!que.empty())que.pop(); que.push(st); memset(g,-1,sizeof(g)); cnt=0; g[st]=cnt++; while(!que.empty()) { int x=que.front(); que.pop(); for(int i=1;i<=m;i++) { if(!zero(p[i]))continue; int y=(i+x)%n; if(g[y]==-1) { g[y]=cnt++; que.push(y); } } } } int main() { int T,d; scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&n,&m,&ed,&st,&d); for(int i=1;i<=m;i++) { scanf("%lf",&p[i]); p[i]=1.0*p[i]/100.0; } if(ed==st) { puts("0.00"); continue; } n=2*n-2; if(d==1)st=n-st; bfs(); if(g[ed]==-1&&g[n-ed]==-1){ puts("Impossible !"); continue; } memset(a,0,sizeof(a)); for(int i=0;i<n;i++) { if(g[i]==-1)continue; if(i==ed||i==n-ed) { a[g[i]][g[i]]=1; a[g[i]][cnt]=0; continue; } a[g[i]][g[i]]=1.0; for(int j=1;j<=m;j++) { int y=(i+j)%n; if(g[y]==-1)continue; a[g[i]][g[y]]-=p[j]; a[g[i]][cnt]+=1.0*j*p[j]; } } if(!guss(cnt))puts("Impossible !"); else printf("%.2lf\n",a[g[st]][cnt]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。