来自蒟蒻XXJ的学习记录

可以看《浅析竞赛中一类数学期望问题的解决方法》汤可因

#include
    
     #define mem(i,j) memset(i,j,sizeof(i))#define GO(i,here) for(int i=head[here];i!=-1;i=nex[i])using namespace std;const int MAXN=1024;const int MAXE=2048;inline int in(){    int a(0);char c=getchar();    while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();    return a;}int n,e,c,m;int head[MAXN],to[MAXE],nex[MAXE],top1;int p[MAXN][MAXN],vis[MAXN];double f[MAXN][MAXN],t[MAXN];queue
     
       q;void bfs(int s){    q.push(s);mem(vis,-1);    vis[s]=0;    while(!q.empty()){        int here=q.front();q.pop();        GO(i,here){            if(vis[to[i]]==vis[here]+1) p[s][to[i]]=min(p[s][to[i]],p[s][here]);            if(vis[to[i]]>=0) continue;            p[s][to[i]]=p[s][here];            if(s==here) p[s][to[i]]=to[i];            vis[to[i]]=vis[here]+1;            q.push(to[i]);        }    }}void add(int a,int b){    nex[top1]=head[a];head[a]=top1;to[top1++]=b;    nex[top1]=head[b];head[b]=top1;to[top1++]=a;}double dp(int a,int b){    if(f[a][b]) return f[a][b];    if(a==b) return 0;    if(p[a][b]==b||p[p[a][b]][b]==b) return f[a][b]=1;    double tot=dp(p[p[a][b]][b],b);    GO(i,b){        int tmp=to[i];        tot+=dp(p[p[a][b]][b],to[i]);    }    f[a][b]=tot/(t[b]+1.0)+1.0;    return f[a][b];}void input(){    mem(head,-1);    n=in();e=in();    c=in();m=in();    for(int i=1;i<=e;i++){        int a,b;        a=in();b=in();        add(a,b);        ++t[a];++t[b];    }    for(int i=1;i<=n;i++)        bfs(i);}void xxj(){    cout<
      
       <
       
        <
        
         <