首页 > 代码库 > BZOJ 2878: [Noi2012]迷失游乐园
BZOJ 2878: [Noi2012]迷失游乐园
题目链接
题意：
给你一张n个点n-1或n条边的带权无向图。从每个点出发一直走下去，不能重复经过某个点。问走过的路径长度的数学期望是多少？
N<=100000。图中至多只有一个环，并且环长不超过20。
题解:
首先考虑是一颗树的情况：
首先随便取一个点为根（例如1号点），做树状动规。
设点i走向它的子树的期望长度为F[i]，i的子节点为s1、s2……sk。
设D[i] = ∑( F[sj] + edge(i,sj) ) ，那么F[i] = D[i] / k。
设P[i]为i作为起点的期望长度，那么P[1]=F[1]，Du[i]是节点i的度数。
再进行一次DFS，如果y是x的子节点，P[x]已经算出。
设节点y向x走对期望的贡献是other，other=(P[x]*Du[x]-edge(x,y)-F[x])/(Du[x]-1)+edge(x,y)
P[y]=(other+D[y])/Du[y]
这样通过两次DFS，就可以算出所有点的P值。
但是这个题可能是一颗基环树。
首先可以通过dfs找出这个环，如果去掉这个环，那就是一些子树构成的森林。
首先用前面提到的树形动规的方法处理这些子树，求出D和F。
然后注意到环上的点很少，我们就依次让环上的每个点作为起点计算一遍。
对于环上的点x，设calc_pre(x)为从x向环上左侧走得到的期望长度，calc_nxt(x)为从x向环上右侧走得到的期望长度。
sx为x的孩子。
那么P[x]=(∑(F[sx]+edge(x,sx)+calc_pre(x)+calc_nxt(x))/Du(x)。
其中calc_pre,calc_nxt可以O(环上点个数)复杂度求出。
于是就可以再次dfs算出所有点的P。
ans=(∑P[i])/n
/************************************************************** Problem: 2878 User: zrts Language: C++ Result: Accepted Time:588 ms Memory:10748 kb****************************************************************/ #include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>//by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);bool oncircle[100005];int du[100005];int fa[100005];int H[100005],X[200005],P[200005],tot;double E[200005];inline void add(int x,int y,int z){//add an edge P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;}int n,m;double F[100005];//for son Edouble D[100005];// F * |son|double p[100005];// ansint num[100005];// |son|int pre[100005];double wpre[100005];bool type;void treedp1(int x){//Dp the tree first for(int i=H[x];i;i=X[i]){ if(P[i]==fa[x]||oncircle[P[i]]) continue; fa[P[i]]=x; treedp1(P[i]); D[x]+=F[P[i]]+E[i];num[x]++; } if(num[x]) F[x]=D[x]/num[x]; else F[x]=0;}void treedp2(int x,double edge){//Dp the tree second | calc the P double other; if(!fa[fa[x]]) { if(!type){ if(num[fa[x]]>1) other=(p[fa[x]]*(num[fa[x]]+0)-edge-F[x])/(num[fa[x]]-1)+edge; else other=edge; }else{ other=(p[fa[x]]*(num[fa[x]]+2)-edge-F[x])/(num[fa[x]]+1)+edge; } } else other=(p[fa[x]]*(num[fa[x]]+1)-edge-F[x])/num[fa[x]]+edge; p[x]=(other+D[x])/(num[x]+1); for(int i=H[x];i;i=X[i]){ if(P[i]==fa[x]||oncircle[P[i]]) continue; treedp2(P[i],E[i]); }}vector<int> circle;bool ok;int nxt[100005];double wnxt[100005];void findcircle(int x,int fa){ for(int i=H[x];i;i=X[i]){ if(P[i]==fa) continue; if(pre[P[i]]){ ok=1; int k=x; pre[P[i]]=x; wpre[P[i]]=E[i]; do{ oncircle[k]=1; circle.push_back(k); k=pre[k]; }while(k!=P[i]); oncircle[k]=1; circle.push_back(k); }else{ pre[P[i]]=x;wpre[P[i]]=E[i]; findcircle(P[i],x); if(ok) return; } }}double calc_nxt(int now,int end){ double ret=wnxt[now]; now=nxt[now]; int extra=0; if(nxt[now]!=end) ret+=calc_nxt(now,end)/(du[now]-1); else extra=-1; for(int i=H[now];i;i=X[i]){ if(oncircle[P[i]]) continue; ret+=(E[i]+F[P[i]])/(du[now]-1+extra); } return ret;}double calc_pre(int now,int end){ double ret=wpre[now]; now=pre[now]; int extra=0; if(pre[now]!=end) ret+=calc_pre(now,end)/(du[now]-1); else extra=-1; for(int i=H[now];i;i=X[i]){ if(oncircle[P[i]]) continue; ret+=(E[i]+F[P[i]])/(du[now]-1+extra); } return ret;}int main(){// the main function #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d%d",&n,&m); for(int i=0,x,y,z;i<m;i++){ scanf("%d%d%d",&x,&y,&z); du[x]++; du[y]++; add(x,y,z); add(y,x,z); } if(m==n-1){ treedp1(1); p[1]=F[1]; for(int i=H[1];i;i=X[i]){ treedp2(P[i],E[i]); } double ans=0; for(int i=1;i<=n;i++){ ans+=p[i]; } printf("%.5f\n",ans/n); }else{ type=1; pre[1]=-1; findcircle(1,-1); for(int now=0;now<circle.size();now++){ nxt[pre[circle[now]]]=circle[now]; wnxt[pre[circle[now]]]=wpre[circle[now]]; } for(int now=0;now<circle.size();now++){ for(int i=H[circle[now]];i;i=X[i]){ if(oncircle[P[i]]) continue; treedp1(P[i]); p[circle[now]]+=(F[P[i]]+E[i])/du[circle[now]]; num[circle[now]]++; } } for(int now=0;now<circle.size();now++){ p[circle[now]]+=(calc_pre(circle[now],circle[now])+calc_nxt(circle[now],circle[now]))/du[circle[now]]; } for(int now=0;now<circle.size();now++){ for(int i=H[circle[now]];i;i=X[i]){ if(oncircle[P[i]]) continue; fa[P[i]]=circle[now]; treedp2(P[i],E[i]); } } double ans=0; for(int i=1;i<=n;i++){ ans+=p[i]; } printf("%.5f\n",ans/n); } return 0;}
BZOJ 2878: [Noi2012]迷失游乐园
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。