BZOJ3270 博物馆(高斯消元+概率期望)

  将两个人各自所在点视为状态,新建一个图。到达某个终点的概率等于其期望次数。那么高斯消元即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 410
int n,m,s,t,d[][],degree[];
double a[N][N],p[];
int trans(int x,int y){return (x-)*n+y;}
void gauss()
{
for (int i=;i<n*n;i++)
{
int mx=i;
for (int j=i+;j<=n*n;j++)
if (fabs(a[j][i])>fabs(a[mx][i])) mx=j;
if (mx!=i) swap(a[i],a[mx]);
for (int j=i+;j<=n*n;j++)
{
double t=a[j][i]/a[i][i];
for (int k=i;k<=n*n+;k++)
a[j][k]-=t*a[i][k];
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj3270.in","r",stdin);
freopen("bzoj3270.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read(),s=read(),t=read();
for (int i=;i<=m;i++)
{
int x=read(),y=read();
degree[x]++,degree[y]++;
d[x][y]=d[y][x]=;
}
for (int i=;i<=n;i++) d[i][i]=;
for (int i=;i<=n;i++) cin>>p[i];
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
for (int x=;x<=n;x++)
for (int y=;y<=n;y++)
if (x!=y&&d[x][i]&&d[y][j])
{
if (x==i) a[trans(i,j)][trans(x,y)]=p[x];
else if (d[x][i]) a[trans(i,j)][trans(x,y)]=(-p[x])/degree[x];
if (y==j) a[trans(i,j)][trans(x,y)]*=p[y];
else if (d[y][j]) a[trans(i,j)][trans(x,y)]*=(-p[y])/degree[y];
}
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
a[trans(i,j)][trans(i,j)]--;
a[trans(s,t)][n*n+]=-;
gauss();
for (int i=n*n;i>=;i--)
{
a[i][n*n+]/=a[i][i];
for (int j=i-;j;j--)
a[j][n*n+]-=a[i][n*n+]*a[j][i];
}
for (int i=;i<=n;i++) printf("%.6lf ",a[trans(i,i)][n*n+]);
return ;
}
上一篇:使用spring声明式事务,spring使用AOP来支持声明式事务,会根据事务属性,自动在方法调用之前决定是否开启一个事务,并在方法执行之后决定事务提交或回滚事务。


下一篇:利用VS2008发布一个简单的webservice