【BZOJ1415】 [Noi2005]聪聪和可可概率与期望

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

其实题不难，不知提交了几次。。。不能代码MD。。。注意一些基本问题。。。SB概率题

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 1001

 using namespace std;

 double f[N][N];

 int n,m,cnt,a,b;

 struct E{int next,to;}e[*N+];

 int head[N],ds[N],q[N],dis[N][N],p[N][N];

 inline int read()

 {

     int ans=,f=;

     char c;

     while (!isdigit(c=getchar())) if (c=='-') f=-;

     ans=c-'';

     while (isdigit(c=getchar())) ans=ans*+c-'';

     return ans*f;

 }

 void insert(int u,int v)

 {

     cnt++; e[cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; ds[u]++;

     cnt++; e[cnt].next=head[v]; head[v]=cnt; e[cnt].to=u; ds[v]++;

 }

 double DP(int x,int y)

 {

     if (f[x][y]) return f[x][y];

     if (x==y) return ;

     if (p[x][y]==y || p[p[x][y]][y]==y) return f[x][y]=;

     double tot=DP(p[p[x][y]][y],y);

     for (int i=head[y];i;i=e[i].next)

         tot+=DP(p[p[x][y]][y],e[i].to);

     return f[x][y]=tot/(ds[y]+)+;

 }

 void Bfs(int x)

 {

     int t=,w=;

     q[t]=x;

     dis[x][x]=;

     while (t!=w)

     {

         int now=q[t],tmp=p[x][now];

         t++; if (t==) t=;

         for (int i=head[now];i;i=e[i].next)

             if (dis[x][e[i].to]==- || (dis[x][e[i].to]==dis[x][now]+ && tmp<p[x][e[i].to]))

             {

                 dis[x][e[i].to]=dis[x][now]+;

                 p[x][e[i].to]=tmp;

                 if (!tmp) p[x][e[i].to]=e[i].to;

                 q[w]=e[i].to;

                 w++; if (w==) w=;

             }

     }

 }

 int main()

 {

     memset(dis,-,sizeof(dis));

     n=read(); m=read(); a=read(); b=read();

     for (int i=;i<=m;i++)

     {

         int u,v;

         u=read(); v=read();

         insert(u,v);

     }

     for (int i=;i<=n;i++) Bfs(i);

     printf("%.3lf",DP(a,b));

     return ;

 }