Aimee

做了一下午期望dp

终于一遍过zi

转移的方式很好想

但是瞬移怎么解决，既然瞬移是直接到头的话，并且保证出发点不相同

的话，那么并查集完成瞬移操作

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring> 
using namespace std;
int n,m;
int fa[100001];
int x,y;
double dp[100001];
int find(int x){
    return x==fa[x] ? x:fa[x]=find(fa[x]);
}
int main(){
    while(scanf("%d%d",&n,&m)){
        if(n==0&m==0)
        return 0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n+6;++i)
            fa[i]=i;
        for(int i=1;i<=m;++i){
            scanf("%d%d",&x,&y);
            x++;
            y++;
            fa[x]=y;
        }
        for(int i=n;i>=1;--i){
            for(int j=1;j<=6;++j){
                dp[i]+=dp[find(i+j)]/6;
            }
            dp[i]+=1.0;
        }
        printf("%.4lfn",dp[1]);
    }
    return 0;
}