聪聪和可可

Description

Input

数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output

输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Sample Input

【输入样例1】
4 3
1 4
1 2
2 3
3 4
【输入样例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output

【输出样例1】
1.500
【输出样例2】
2.167

HINT

【样例说明1】
开始时，聪聪和可可分别在景点1和景点4。
第一个时刻，聪聪先走，她向更靠近可可(景点4)的景点走动，走到景点2，然后走到景点3；假定忽略走路所花时间。
可可后走，有两种可能：
第一种是走到景点3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为1，概率为。
第二种是停在景点4，不被吃掉。概率为。
到第二个时刻，聪聪向更靠近可可(景点4)的景点走动，只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1* +2* =1.5步。

对于所有的数据，1≤N,E≤1000。
对于50%的数据，1≤N≤50。

solution：

先预处理出来一个表f[i][j]，表示聪聪在i时，可可在j时，聪聪走一步时的最优
(我一开始处理了一个走一步和两步一共的最优，是错误的，因为有的奇怪情况会..)

为了处理这个表，可以用n遍spfa，
网上大神说这是个稀疏图，稀疏图用spfa比较快

然后就是记忆化dfs(感觉最近dfs用的有点多)，一定要记忆化，否则会超3个点
int kk=f[f[i][j]][j]
设temp为与j相连的点
dp[i][j]=1+(sigma(dp[kk][temp])+dp[kk][j])/(1+outdegree[j]);
1的意思是从i走到kk
(sigma(dp[kk][temp])+dp[kk][j])枚举可可的几种情况，并且聪聪先走
(1+outdegree[j])就是概率

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 #include<ctime>
  7 #define dd double
  8 #define mem(a,b) memset(a,b,sizeof(a))
  9 using namespace std;
 10 int maxn(int a,int b){return a>b?a:b;}
 11 int minn(int a,int b){return a<b?a:b;}
 12 struct son
 13 {
 14     int v,next;
 15 };
 16 son a1[2001];
 17 int first[2001],e;
 18 
 19 void addbian(int u,int v)
 20 {
 21     a1[e].v=v;
 22     a1[e].next=first[u];
 23     first[u]=e++;
 24 }
 25 
 26 double outdegree[2001];
 27 double gai[2001];
 28 int f[2001][2001];//猫在i 老鼠在j时 下一步的选择 
 29 
 30 double ans;
 31 
 32 int n,m,kk,cc;
 33 int u,o,p;
 34 int vis[2001];
 35 struct son1
 36 {
 37     int val,order;
 38 };
 39 queue<int> q;
 40 int d[2001][2001];
 41 double dp[2001][2001];
 42 
 43 void dfs(int cc,int kk)
 44 {
 45     //printf("cc=%d kk=%d bushu=%d gailu=%.19lf
",cc,kk,bushu,gailu);
 46     if(dp[cc][kk])
 47       return ;
 48     if(cc==kk)//可可自己送上门来 
 49     {
 50         //ans+=(dd)bushu*gailu;
 51         dp[cc][kk]=0;
 52         return ;
 53     }
 54     if(f[cc][kk]==kk||f[f[cc][kk]][kk]==kk)//聪聪先走，吃了可可 
 55     {
 56       //ans+=(dd)(bushu+1)*gailu;
 57       dp[cc][kk]=1;
 58       return ;
 59     }
 60     dfs(f[f[cc][kk]][kk],kk);
 61     dp[cc][kk]+=dp[f[f[cc][kk]][kk]][kk];
 62     for(int i=first[kk];i!=-1;i=a1[i].next)
 63     {
 64         int temp=a1[i].v;
 65         dfs(f[f[cc][kk]][kk],temp);
 66         dp[cc][kk]+=dp[f[f[cc][kk]][kk]][temp];
 67     }
 68     dp[cc][kk]/=(1.0+(dd)outdegree[kk]);
 69     dp[cc][kk]+=1.0;
 70     return ;
 71 }
 72 
 73 int spfa(int x)
 74 {
 75     mem(vis,0);
 76     mem(d[x],0x7f/3);
 77     vis[x]=1;
 78     q.push(x);
 79     d[x][x]=0;
 80     while(!q.empty())
 81     {
 82         int k=q.front();
 83         vis[k]=0;
 84         q.pop();
 85         for(int i=first[k];i!=-1;i=a1[i].next)
 86         {
 87             int temp=a1[i].v;
 88             if(d[x][temp]>d[x][k]+1)
 89             {
 90                 d[x][temp]=d[x][k]+1;
 91                 if(!vis[temp])
 92                 {
 93                     q.push(temp);
 94                     vis[temp]=1;
 95                 }
 96             }
 97         }
 98     }
 99 }
100 
101 
102 void SPFA()
103 {
104     for(int i=1;i<=n;++i)
105         spfa(i);
106     
107     int minl,order;
108     for(int k=1;k<=n;++k)
109       for(int i=1;i<=n;++i)
110       {
111             minl=d[i][k];order=i;
112           for(int j=first[i];j!=-1;j=a1[j].next)
113         {
114                 int temp=a1[j].v;
115                 if(d[temp][k]==minl)
116                   order=minn(order,temp);
117                 else
118                   if(d[temp][k]<minl)
119                   {
120                         minl=d[temp][k];
121                         order=temp;
122                     }
123             }
124             f[i][k]=order;
125         }    
126 }
127 
128 void out11()
129 {
130     printf("
");
131     for(int i=1;i<=n;++i)
132     {
133         for(int j=1;j<=n;++j)
134           printf("%d ",d[i][j]);
135         printf("
");
136     }
137     printf("
");
138     for(int i=1;i<=n;++i)
139     {
140         for(int j=1;j<=n;++j)
141           printf("%d ",f[i][j]);
142         printf("
");
143     }
144     printf("
");
145     /*for(int i=1;i<=n;++i)
146     {
147         for(int j=1;j<=n;++j)
148           printf("%.3lf ",dp[i][j]);
149         printf("
");
150     }
151     printf("
");*/
152 }
153 
154 int main(){
155     //freopen("1.txt","r",stdin);
156     freopen("cchkk.in","r",stdin);
157     freopen("cchkk.out","w",stdout);
158     //freopen("3.txt","w",stdout);
159     mem(first,-1);
160     scanf("%d%d%d%d",&n,&m,&cc,&kk);
161     for(int i=1;i<=m;++i)
162     {
163         scanf("%d%d",&u,&o);
164         ++outdegree[u];
165         ++outdegree[o];
166         addbian(u,o);
167         addbian(o,u);
168     }
169     SPFA();
170     //printf("time=%d
",clock());
171     for(int i=1;i<=n;++i)
172       gai[i]=1.0/(outdegree[i]+1.0);
173     //cout<<0;
174     dfs(cc,kk);
175     //out11();
176     //printf("%.3lf",dp[cc][kk]);
177     printf("%.3lf",dp[cc][kk]);
178     //while(1);
179     return 0;
180 }

View Code

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 #include<ctime>
  7 #define dd double
  8 #define mem(a,b) memset(a,b,sizeof(a))
  9 using namespace std;
 10 int maxn(int a,int b){return a>b?a:b;}
 11 int minn(int a,int b){return a<b?a:b;}
 12 struct son
 13 {
 14     int v,next;
 15 };
 16 son a1[2001];
 17 int first[2001],e;
 18  
 19 void addbian(int u,int v)
 20 {
 21     a1[e].v=v;
 22     a1[e].next=first[u];
 23     first[u]=e++;
 24 }
 25  
 26 double outdegree[2001];
 27 double gai[2001];
 28 int f[2001][2001];//猫在i 老鼠在j时 下一步的选择 
 29  
 30 double ans;
 31  
 32 int n,m,kk,cc;
 33 int u,o,p;
 34 int vis[2001];
 35 struct son1
 36 {
 37     int val,order;
 38 };
 39 queue<int> q;
 40 int d[2001][2001];
 41  
 42 void dfs(int cc,int kk,int bushu,double gailu)
 43 {
 44     //printf("cc=%d kk=%d bushu=%d gailu=%.3lf
",cc,kk,bushu,gailu);
 45     if(cc==kk)//可可自己送上门来 
 46     {
 47         ans+=(dd)bushu*gailu;
 48         return ;
 49     }
 50     if(f[cc][kk]==kk||f[f[cc][kk]][kk]==kk)//聪聪先走，吃了可可 
 51     {
 52       ans+=(dd)(bushu+1)*gailu;
 53       return ;
 54     }
 55     
 56     dfs(f[f[cc][kk]][kk],kk,bushu+1,gailu*gai[kk]);
 57     //dp[cc][kk]+=dp[f[cc][kk]][kk];
 58     for(int i=first[kk];i!=-1;i=a1[i].next)
 59     {
 60         int temp=a1[i].v;
 61         dfs(f[f[cc][kk]][kk],temp,bushu+1,gailu*gai[kk]);
 62         //dp[cc][kk]+=dp[f[cc][kk]][temp];
 63     }
 64     //dp[cc][kk]/=(1.0+(dd)outdegree[kk]);
 65     //dp[cc][kk]+=1.0;
 66 }
 67  
 68 int spfa(int x)
 69 {
 70     mem(vis,0);
 71     mem(d[x],0x7f/3);
 72     vis[x]=1;
 73     q.push(x);
 74     d[x][x]=0;
 75     while(!q.empty())
 76     {
 77         int k=q.front();
 78         vis[k]=0;
 79         q.pop();
 80         for(int i=first[k];i!=-1;i=a1[i].next)
 81         {
 82             int temp=a1[i].v;
 83             if(d[x][temp]>d[x][k]+1)
 84             {
 85                 d[x][temp]=d[x][k]+1;
 86                 if(!vis[temp])
 87                 {
 88                     q.push(temp);
 89                     vis[temp]=1;
 90                 }
 91             }
 92         }
 93     }
 94 }
 95  
 96  
 97 void SPFA()
 98 {
 99     for(int i=1;i<=n;++i)
100         spfa(i);
101     
102     int minl,order;
103     for(int k=1;k<=n;++k)
104       for(int i=1;i<=n;++i)
105       {
106             minl=d[i][k];order=i;
107           for(int j=first[i];j!=-1;j=a1[j].next)
108         {
109                 int temp=a1[j].v;
110                 if(d[temp][k]==minl)
111                   order=minn(order,temp);
112                 else
113                   if(d[temp][k]<minl)
114                   {
115                         minl=d[temp][k];
116                         order=temp;
117                     }
118             }
119             f[i][k]=order;
120         }    
121 }
122  
123 void out11()
124 {
125     printf("
");
126     for(int i=1;i<=n;++i)
127     {
128         for(int j=1;j<=n;++j)
129           printf("%d ",d[i][j]);
130         printf("
");
131     }
132     printf("
");
133     for(int i=1;i<=n;++i)
134     {
135         for(int j=1;j<=n;++j)
136           printf("%d ",f[i][j]);
137         printf("
");
138     }
139     printf("
");
140     /*for(int i=1;i<=n;++i)
141     {
142         for(int j=1;j<=n;++j)
143           printf("%.3lf ",dp[i][j]);
144         printf("
");
145     }
146     printf("
");*/
147 }
148  
149 int main(){
150     //freopen("1.txt","r",stdin);
151     freopen("cchkk.in","r",stdin);
152     freopen("cchkk.out","w",stdout);
153     //freopen("3.txt","w",stdout);
154     mem(first,-1);
155     scanf("%d%d%d%d",&n,&m,&cc,&kk);
156     for(int i=1;i<=m;++i)
157     {
158         scanf("%d%d",&u,&o);
159         ++outdegree[u];
160         ++outdegree[o];
161         addbian(u,o);
162         addbian(o,u);
163     }
164     SPFA();
165     //printf("time=%d
",clock());
166     for(int i=1;i<=n;++i)
167       gai[i]=1.0/(outdegree[i]+1.0);
168     //cout<<0;
169     dfs(cc,kk,0,1.0);
170     //out11();
171     //printf("%.3lf",dp[cc][kk]);
172     printf("%.3lf",ans);
173     //while(1);
174     return 0;
175 }

暴力