5
10
2016
0

[BZOJ1415] [Noi2005]聪聪和可可

图上进行概率DP

先BFSn次算出每个点的最优前进点

然后对于每种情况DFS算期望

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=1005;
 
int n,m,en,h[N],deg[N],Cat,Mouse,D[N][N],P[N][N];
double f[N][N];
queue<int> Q;
 
struct Edge{
int b,next;
}e[N*2];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
deg[sa]++;
}
 
void BFS(int S){
Q.push(S);
D[S][S]=0;
while(!Q.empty()){
    int u=Q.front(),tmp=P[S][u];
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[S][v]==-1 || (D[S][u]+1==D[S][v] && tmp<P[S][v])){
            D[S][v]=D[S][u]+1;
            if(!tmp)P[S][v]=v;
            else P[S][v]=tmp;
            Q.push(v);
        }
    }
}
}
 
double DP(int Cat,int Mouse){
if(f[Cat][Mouse])return f[Cat][Mouse];
if(Cat==Mouse)return f[Cat][Mouse]=0;
if(P[Cat][Mouse]==Mouse || P[P[Cat][Mouse]][Mouse]==Mouse)return f[Cat][Mouse]=1;
double Sum=DP(P[P[Cat][Mouse]][Mouse],Mouse);
for(int i=h[Mouse];i;i=e[i].next)Sum+=DP(P[P[Cat][Mouse]][Mouse],e[i].b);
return f[Cat][Mouse]=Sum/(deg[Mouse]+1)+1;
}
 
int main(){
freopen("1415.in","r",stdin);
freopen("1415.out","w",stdout);
memset(D,-1,sizeof(D));
scanf("%d %d %d %d",&n,&m,&Cat,&Mouse);
for(int i=1;i<=m;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    AddEdge(sa,sb);
    AddEdge(sb,sa);
}
for(int i=1;i<=n;i++)BFS(i);
printf("%.3lf\n",DP(Cat,Mouse));
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 453

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com