luogu P4206 聪聪和可可

聪聪和可可

鸽了两天

\(dijkstra\)预处理出来两点之间的最短路径\(dis\)数组，读题发现，\(cat\)的走位很怪sb斩了，所以我们设一个\(next\)数组，\(next[i][j]\)表示\(cat\)在\(i\)位置，\(mouse\)在\(j\)位置时，\(cat\)下一步要去的位置，

设\(i\),\(j\)之间有一条边则

\[if\left(dis[i][k]-1==dis[k][j]\right) \\
next[i][k]=\min(next[i][k],j)
\]

考虑答案的转移，设\(u\)为\(cat\)当前所在的位置，\(v\)为\(mouse\)当前所在的位置，\(a\)为\(cat\)走一步所到的位置，\(b\)为\(cat\)走两步所到的位置，\(to\)为\(mouse\)可到达的位置最后记得算上一开始的v，\(du\)数组为该点的出度记得加上自己，则有以下三种情况

\[if\left(u==v\right)\;\;return 0; \\
if(a==v||b==v)\;\;return 1; \\
else\;\;dp[u][v]+=\frac{dfs\left(b,to\right)}{\left(du[v]+1\right)}
\]

最后记得算上\(mouse\)一开始所在的位置\(v\)

\[dp[u][v]+=\frac{dfs\left(b,v\right)}{\left(du[v]+1\right)}
\]

以上求答案的过程可用\(dfs\)解决

Code：

#include<cstdio>

#include<queue>

#define MAX 1001

#define re register

#define INF 114514

namespace OMA

{

   int n,e,c,m;

   int dis[MAX][MAX];

   int cnt=1,head[MAX];

   int du[MAX],next[MAX][MAX];

   double dp[MAX][MAX];

   bool pre[MAX],vis[MAX][MAX];

   struct node

   {

     int next;

     int to;

   }edge[MAX<<1];

   typedef std::pair<int,int>oma;

   std::priority_queue<oma,std::vector<oma>,std::greater<oma> >q;

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline void add(int u,int v)

   {

     edge[++cnt].next = head[u];

     edge[cnt].to = v;

     head[u] = cnt;

   }

   inline int min(int a,int b)

   { return a<b?a:b; }

   void in()

   {

     n=read(),e=read(),c=read(),m=read();

     for(re int i=1; i<=e; i++)

     {

       int u=read(),v=read();

       add(u,v),add(v,u);

       du[u]++,du[v]++;

     }

     for(re int i=1; i<=n; i++)

     {

       for(re int j=1; j<=n; j++)

       { next[i][j] = INF; }

     }

   }

   inline void dijkstra(int u)

   {

     for(re int i=1; i<=n; i++)

     { dis[u][i] = INF ,pre[i] = false; }

     while(!q.empty())

     { q.pop(); }

     dis[u][u] = 0;

     q.push(std::make_pair(0,u));

     while(!q.empty())

     {

       int k = q.top().second;

       q.pop();

       if(pre[k])

       { continue; }

       pre[k] = true;

       for(re int i=head[k]; i; i=edge[i].next)

       {

         int to = edge[i].to;

         if(!pre[to]&&(dis[u][to]>dis[u][k]+1))

         {

           dis[u][to] = dis[u][k]+1;

           q.push(std::make_pair(dis[u][to],to));

         }

       }

     }

   }

   inline double dfs(int cat,int mouse)

   {

     if(vis[cat][mouse])

     { return dp[cat][mouse]; }

     if(cat==mouse)

     { return 0; }

     int a,b;

     a = next[cat][mouse];

     b = next[a][mouse];

     if(a==mouse||b==mouse)

     { return 1; }

     dp[cat][mouse] = 1;

     for(re int i=head[mouse]; i; i=edge[i].next)

     {

       int to = edge[i].to;

       dp[cat][mouse] += dfs(b,to)/(du[mouse]+1);

     }

     dp[cat][mouse] += dfs(b,mouse)/(du[mouse]+1);

     vis[cat][mouse] = 1;

     return dp[cat][mouse];

   }

   signed main()

   {

     in();

     for(re int i=1; i<=n; i++)

     { dijkstra(i); }

     for(re int i=1; i<=n; i++)

     {

       for(re int j=head[i]; j; j=edge[j].next)

       {

         int to = edge[j].to;

         for(re int k=1; k<=n; k++)

         {

           if(dis[i][k]-1==dis[k][to])

           { next[i][k] = min(next[i][k],to); }

         }

       }

     }

     printf("%.3lf\n",dfs(c,m));

     return 0;

   }

}

signed main()

{ return OMA::main(); }

巴特西

luogu P4206 聪聪和可可

最新文章

热门文章