首页 > 代码库 > 博物馆 bzoj3270
博物馆 bzoj3270
首先最难想的是两个人要在同一时间,同一地点相遇,这样很难处理,所以用类似于聪聪和可可的方法,用f[i][j]表示A在i位置,B在j位置,那么f[i][j]的转移方法就有四个
1、两个人都在原地没动,则a[f[i][j]]+=a[f[i][j]]*p[i]*p[j];
2(3)、其中有一个人动,以A动为例 a[f[i][j]]+=p[j]*((1-p[v]).chu[v])*a[f[v][j]];
4、两人都动,类比2即可.
注意到f是一个矩阵,所以将其编号,之后用高斯消元,接触每一个f[i][i]的值,就是答案;
1 #include<cmath> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 struct Node{ 9 int u,v,nxt; 10 }g[400]; 11 int n,m,A,B; 12 int chu[25]; 13 int adj[400],e; 14 int f[21][21]; 15 double p[25]; 16 double a[410][410]; 17 double ans[410]; 18 void add(int u,int v){ 19 g[++e].v=v; g[e].u=u; 20 g[e].nxt=adj[u]; adj[u]=e; 21 } 22 void gs(){ 23 int N=n*n+1; 24 int T=n*n; 25 int h=1,num; 26 for(int i=1;i<T;i++,h++){ 27 num=h; 28 for(int j=h+1;j<=T;j++){ 29 if(fabs(a[j][i]) > fabs(a[num][i])) num=j; 30 } 31 if(num!=h){ 32 for(int j=i;j<=N;j++){ 33 swap(a[h][j],a[num][j]); 34 } 35 } 36 if(a[h][i]==0){ 37 h--; 38 continue; 39 } 40 double ti; 41 for(int j=h+1;j<=T;j++){ 42 if(a[j][i]==0) continue; 43 ti=a[j][i]/a[h][i]; 44 for(int k=i;k<=N;k++){ 45 a[j][k]-=a[h][k]*ti; 46 } 47 } 48 } 49 for(int i=T;i>=1;i--){ 50 for(int j=i+1;j<=T;j++){ 51 a[i][N]-=a[i][j]*ans[j]; 52 } 53 ans[i]=a[i][N]/a[i][i]; 54 } 55 56 } 57 int main(){ 58 freopen("a.in","r",stdin); 59 scanf("%d%d%d%d",&n,&m,&A,&B); 60 int x,y; 61 for(int i=1;i<=m;i++){ 62 scanf("%d%d",&x,&y); 63 add(x,y); add(y,x); 64 chu[x]++; chu[y]++; 65 } 66 for(int i=1;i<=n;i++){ 67 add(i,i); 68 scanf("%lf",&p[i]); 69 } 70 memset(a,0,sizeof(a)); 71 int v1,v2; 72 int R; 73 a[(A-1)*n+B][n*n+1]=-1; 74 for(int i=1;i<=n;i++){ 75 for(int j=1;j<=n;j++){ 76 R=(i-1)*n+j; 77 a[R][R]=-1; 78 for(int k=adj[i];k;k=g[k].nxt){ 79 v1=g[k].v; 80 for(int h=adj[j];h;h=g[h].nxt){ 81 v2=g[h].v; 82 if(v1==v2) continue; 83 if(v1==i && v2==j){ 84 a[R][(i-1)*n+j]+=p[i]*p[j]; 85 } 86 else if(v1==i && v2!=j){ 87 a[R][(v1-1)*n+v2]+=p[v1]*((1-p[v2])); 88 } 89 else if(v1!=i && v2==j){ 90 a[R][(v1-1)*n+v2]+=p[v2]*((1-p[v1])); 91 } 92 else if(v1!=i && v2!=j){ 93 a[R][(v1-1)*n+v2]+=((1-p[v1]))*((1-p[v2])); 94 } 95 } 96 } 97 } 98 } 99 gs(); 100 for(int i=1;i<=n;i++){ 101 R=(i-1)*n+i; 102 // cout<<"R== "<<" "<<R<<endl; 103 printf("%.6lf ",ans[R]); 104 } 105 return 0; 106 }
博物馆 bzoj3270
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。