@OceanEye7年前
04/21
13:30
这是一份简单的题解
用一个二元组表示两个人的状态 (A,B)
然后在二元组里面跑概率方程
稍微参照了一下黄学长的方程列法
不过还是觉得在 起点(A,B) 那里可以更漂亮的。
都一样啦过了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #define db double #define eps 1e-6 using namespace std; #define N 440 #define BASE 20 vector <int> G[BASE+1]; int n,m,___,b,siz,out[BASE+1]; //int G[N][N]; db a[N][N],C[BASE+1]; #define calc(x,y) (x-1)*n+y void build(int _,int __) { int pt=calc(_,__),cur,_1,_2; a[pt][pt]--; for(int i=0;i<G[_].size();i++) for(int j=0;j<G[__].size();j++) { _1=G[_][i]; _2=G[__][j]; cur=calc(_1,_2); if(_1==_2) continue; if(_1==_&&_2==__) a[pt][cur]+=C[_1]*C[_2]; else if(_1==_) a[pt][cur]+=C[_1]*(1-C[_2])/out[_2]; else if(_2==__) a[pt][cur]+=C[_2]*(1-C[_1])/out[_1]; else a[pt][cur]+=(1-C[_2])*(1-C[_1])/out[_1]/out[_2]; } } void pre() { int _,__; db t; scanf("%d %d %d %d",&n,&m,&___,&b); siz=n*n; a[calc(___,b)][siz+1]=-1; for(int i=1;i<=n;i++) G[i].push_back(i); for(int i=1;i<=m;i++) { scanf("%d %d",&_,&__); out[_]++; out[__]++; G[_].push_back(__); G[__].push_back(_); } for(int i=1;i<=n;i++) scanf("%lf",&C[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) build(i,j); } void gauss() { db t; int now=1,to; for(int i=1;i<=siz;i++) { for(to=now;to<=siz;to++) if(abs(a[to][i])>eps) break; if(to>siz) continue; if(to!=now) swap(a[to],a[now]); for(int j=1;j<=siz;j++) { if(j==now) continue; t=a[j][i]/a[now][i]; for(int k=1;k<=siz+1;k++) a[j][k]-=t*a[now][k]; } now++; } } int main() { pre(); gauss(); for(int i=1;i<=n;i++) { printf("%.6lf ",a[calc(i,i)][siz+1]/a[calc(i,i)][calc(i,i)]); } return 0; } |