BZOJ1415 [NOI 2005] 聪聪与可可 -概率与期望-白红宇

BZOJ1415 [NOI 2005] 聪聪与可可 -概率与期望

阅读量：5244 次

发布时间：2019-06-14

本文共 1341 字，大约阅读时间需要 4 分钟。

大致思路

期望题的话，比较容易看出可以用记搜解决。由于每次走的时候要考虑一个距离问题，所以可以预处理出来dis[i][j]表示任意两点间的距离。因为数据范围比较小而且边权均为1，所以可以直接用bfs解决（暴力档弗洛伊德写挂导致少了40分，真实自闭了）。

这里是每次直接考虑走两步，如果走第一步的时候已经到达就返回1，否则就继续往下走第二步。

#include
    
     #define M 1005#define db doubleusing namespace std;bool cur1;int pr[M<<1],to[M<<1],la[M],n,m,tot,S,T,sz[M];void add(int x,int y) {    to[++tot]=y,pr[tot]=la[x],la[x]=tot;}int dis[M][M];db dp[M][M];bool mark[M][M];db dfs(int x,int y) {    if(x==y)return 0;//已经到达了同一个点，可以直接返回    if(mark[x][y])return dp[x][y];//记搜    mark[x][y]=1;    int Mi=1e9,pos=n+1;    for(int i=la[x]; i; i=pr[i]) {        int Y=to[i];        if(dis[Y][y]

Q; bool vis[M]; void bfs(int s,int *Dis) { while(!Q.empty())Q.pop(); Q.push(s); memset(vis,0,sizeof(vis)); Dis[s]=0,vis[s]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=la[x]; i; i=pr[i]) { int y=to[i]; if(vis[y])continue; Dis[y]=Dis[x]+1; vis[y]=1,Q.push(y); } } } void solve() { for(int i=1; i<=n; i++)bfs(i,dis[i]); memset(mark,0,sizeof(mark)); printf("%.3f\n",dfs(S,T)); }} p2;int main() {// printf("%lf\n",(&cur2-&cur1)/1024.0/1024); freopen("cchkk.in","r",stdin); freopen("cchkk.out","w",stdout); scanf("%d%d%d%d",&n,&m,&S,&T); for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); sz[x]++,sz[y]++; add(x,y),add(y,x); } p2.solve(); return 0;}

转载于:https://www.cnblogs.com/cly1231/p/10852576.html

你可能感兴趣的文章