首页 > 代码库 > Bzoj3270 博物馆
Bzoj3270 博物馆
Submit: 456 Solved: 247
Description
有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行，他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间，并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动，去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事：他们并没有选好在哪儿碰面。等时间到六点，他们开始在博物馆里到处乱跑来找到对方（他们没法给对方打电话因为电话漫游费是很贵的）
不过，尽管他们到处乱跑，但他们还没有看完足够的艺术品，因此他们每个人采取如下的行动方法：每一分钟做决定往哪里走，有Pi 的概率在这分钟内不去其他地方（即呆在房间不动），有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事，因此每条走廊会连接两个不同的房间，并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗，两人不可能在走廊碰面，不过他们可以从走廊的两个方向通行。（此外，两个男孩可以同时地穿过同一条走廊却不会相遇）两个男孩按照上述方法行动直到他们碰面为止。更进一步地说，当两个人在某个时刻选择前往同一间房间，那么他们就会在那个房间相遇。
两个男孩现在分别处在a，b两个房间，求两人在每间房间相遇的概率。
Input
第一行包含四个整数，n表示房间的个数;m表示走廊的数目;a,b (1 ≤ a, b ≤ n),表示两个男孩的初始位置。
之后m行每行包含两个整数，表示走廊所连接的两个房间。
之后n行每行一个至多精确到小数点后四位的实数 表示待在每间房间的概率。
题目保证每个房间都可以由其他任何房间通过走廊走到。
Output
输出一行包含n个由空格分隔的数字，注意最后一个数字后也有空格，第i个数字代表两个人在第i间房间碰面的概率（输出保留6位小数）
注意最后一个数字后面也有一个空格
Sample Input
2 1 1 2
1 2
0.5
0.5
1 2
0.5
0.5
Sample Output
0.500000 0.500000
HINT
对于100%的数据有 n <= 20，n-1 <= m <= n(n-1)/2
Source
高斯消元
数学问题 数学概率 高斯消元
用数对(a,b)表示A在a，B在b的状态，则很容易推出各个状态之间的转移概率。如果两人到了相同的位置，就不向其他状态转移
————————
设S为初始行向量(S[(a,b)]=1)，ans为答案行向量
那么有ans=S+SA+SA^2+SA^3+...
——popoQQQ
————————
求一个无限长的多项式的值，可以用1除以它的逆元。
对于矩阵，也可以用单位矩阵I除以矩阵的逆元
于是ans=S(I-A^+∞)/(I-A)
=S/(I-A)
可以得到ans*(I-A)=S
对(I-A)的转置求高斯消元即可得到答案
——————————
一些小花招：
建出转移矩阵以后，大力快速幂，概率会向正确值收敛。
在某道有趣的游戏那边，这么做是可行的，因为矩阵及其小（好像只有20*20），自乘40次就可以得到解了
在这里试图如法炮制，然而400*400的矩阵实在吃不消了233
自乘10次WA，自乘20次T
放弃
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=30; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int v,nxt; 18 }e[200010]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v){ 21 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 22 } 23 int n,m,ed; 24 struct Mat{ 25 double x[401][401]; 26 Mat operator + (const Mat b){ 27 Mat res; 28 for(int i=1;i<=ed;i++) 29 for(int j=1;j<=ed;j++) 30 res.x[i][j]=x[i][j]+b.x[i][j]; 31 return res; 32 } 33 friend Mat operator * (const Mat a,const Mat b){ 34 Mat res; 35 for(int i=1;i<=ed;i++) 36 for(int j=1;j<=ed;j++){ 37 res.x[i][j]=0; 38 for(int k=1;k<=ed;k++) 39 res.x[i][j]+=a.x[i][k]*b.x[k][j]; 40 } 41 return res; 42 } 43 }mt,bas; 44 int out[mxn]; 45 double p[mxn],d[mxn][mxn];; 46 int pa,pb;//初始位置 47 int id[mxn][mxn],cnt=0; 48 void Build(){ 49 int i,j; 50 for(i=1;i<=n;i++) 51 for(j=1;j<=n;j++) 52 id[i][j]=++cnt; 53 ed=cnt; 54 for(i=1;i<=n;i++) 55 for(j=1;j<=n;j++){ 56 if(i==j){ 57 mt.x[id[i][j]][id[i][j]]=1; 58 continue; 59 } 60 for(int k=1;k<=n;k++) 61 for(int l=1;l<=n;l++){ 62 mt.x[id[i][j]][id[k][l]]+=d[i][k]*d[j][l]; 63 // printf("(%d,%d)to(%d,%d):%.3f\n",i,j,k,l,mt.x[id[i][j]][id[k][l]]); 64 } 65 } 66 /* for(i=hd[pa];i;i=e[i].nxt){ 67 int v1=e[i].v; 68 bas.x[id[pa][pb]][id[v1][pb]]=d[pa][v1]*d[pb][pb]; 69 for(j=hd[pb];j;j=e[j].nxt){ 70 int v2=e[j].v; 71 bas.x[id[pa][pb]][id[v1][v2]]=d[pa][v1]*d[pb][v2];//转移 72 } 73 } 74 for(j=hd[pb];j;j=e[j].nxt){ 75 int v2=e[j].v; 76 bas.x[id[pa][pb]][id[pa][v2]]=d[pa][pa]*d[pb][v2]; 77 }*/ 78 return; 79 } 80 int main(){ 81 int i,j,u,v; 82 n=read();m=read();pa=read();pb=read(); 83 for(i=1;i<=m;i++){ 84 u=read();v=read(); 85 add_edge(u,v);add_edge(v,u); 86 ++out[u];++out[v]; 87 } 88 for(i=1;i<=n;i++)scanf("%lf",&p[i]); 89 for(i=1;i<=n;i++){ 90 d[i][i]=p[i]; 91 for(j=hd[i];j;j=e[j].nxt){ 92 int v=e[j].v; 93 d[i][v]+=(1-p[i])/out[i]; 94 } 95 } 96 Build(); 97 // 98 for(i=1;i<=5;i++) mt=mt*mt; 99 // bas=bas*mt;100 /* for(i=1;i<=n;i++)101 for(j=1;j<=n;j++){102 for(int k=1;k<=n;k++)103 for(int l=1;l<=n;l++)104 printf("(%d,%d)to(%d,%d):%.3f\n",i,j,k,l,mt.x[id[i][j]][id[k][l]]);105 }*/106 //107 for(i=1;i<=n;i++)printf("%.6f ",mt.x[id[pa][pb]][id[i][i]]);108 return 0;109 }
——————————
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=30;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 struct edge{17 int v,nxt;18 }e[100010];19 int hd[mxn],mct=0;20 void add_edge(int u,int v){21 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;22 }23 int n,m,ed;24 double f[402][402];25 double ans[402];26 void Gauss(){27 int i,j,k;28 for(i=1;i<=ed;i++){29 int p=i;30 for(j=i+1;j<=ed;j++) if(f[j][i]>f[p][i])p=j;31 if(p!=i)for(j=i;j<=ed+1;j++){swap(f[p][j],f[i][j]);}32 for(j=i+1;j<=ed;j++){33 double x=f[j][i]/f[i][i];34 for(k=i;k<=ed+1;k++){35 f[j][k]-=f[i][k]*x;36 }37 }38 }39 for(i=ed;i;i--){40 for(j=i+1;j<=ed;j++){41 f[i][ed+1]-=f[i][j]*ans[j];42 }43 ans[i]=f[i][ed+1]/f[i][i];44 }45 return;46 }47 int out[mxn];48 double p[mxn],d[mxn][mxn];49 int pa,pb;//初始位置 50 int id[mxn][mxn],cnt=0;51 void Build(){52 int i,j;53 for(i=1;i<=n;i++)54 for(j=1;j<=n;j++)55 id[i][j]=++cnt;56 ed=cnt;57 for(i=1;i<=n;i++)58 for(j=1;j<=n;j++)59 if(i!=j){60 for(int k=1;k<=n;k++)61 for(int l=1;l<=n;l++){62 f[id[i][j]][id[k][l]]-=d[i][k]*d[j][l];63 }64 }65 for(i=1;i<=ed;i++)66 for(j=1;j<i;j++)67 swap(f[i][j],f[j][i]);68 for(i=1;i<=ed;i++)69 f[i][i]+=1;70 f[id[pa][pb]][ed+1]=1;71 return;72 }73 int main(){74 int i,j,u,v;75 n=read();m=read();pa=read();pb=read();76 for(i=1;i<=m;i++){77 u=read();v=read();78 add_edge(u,v);add_edge(v,u);79 ++out[u];++out[v];80 }81 for(i=1;i<=n;i++)scanf("%lf",&p[i]);82 for(i=1;i<=n;i++){83 d[i][i]=p[i];84 for(j=hd[i];j;j=e[j].nxt){85 int v=e[j].v;86 d[i][v]+=(1-p[i])/out[i];87 }88 }89 Build();90 Gauss();91 for(i=1;i<=n;i++)printf("%.6f ",ans[id[i][i]]);92 return 0;93 }
Bzoj3270 博物馆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。