bzoj-2878 迷失游乐园
分类：
题意：
给出一颗树或基环树，树是无向的，边有长度；
一个人随机从树上某结点出发，每次随机选一条边走；
走过的结点不能再走，不能走时停止；
求走的期望长度；
n<=100000
50%的数据给出的图是树；
另50%的数据图为基环树；
基环树的环上结点不超过20个；
题解：
NOI2012的day1t1；
我们先考虑50分的做法；
显然是树形DP，而树形DP的奥义就是强行线性；
恩就是强行线性！
随便拎出来一个点为根，设状态sum[x]为x的儿子结点期望长度之和；
size[x]为x的儿子个数，，fa[x]是x的父树结点期望长度；
然后就是线性乱搞，两个dfs调一调就好了；
至于100分的做法就是环的处理；
暂且把环作为根节点，处理出环上点对于其子树的sum值和子树点分别的sum值；
然后定义对于环上点的fa就是顺时针走环和逆时针走环的期望长度加和；
这样就可以处理子树的fa值了；
但是处理时还要注意一下环上点的fa是二倍的需要分母上多+1；
后面还是代码题了，总之粘代码的时候不要粘错= =；
调一调码一码，2.5kAC。。我感觉我要变成码农的潜质；
SPJ有点bug，见discuss(笑)；
代码：
#include<cstdio>int main(){printf("nan");}啊粘错了；
#include<vector>#include<stdio.h>#include<string.h>#include<algorithm>#define N 110000using namespace std;int to[N<<1],val[N<<1],next[N<<1],head[N],tot;double sum[N],fa[N];int size[N],st[30],top;bool vis[N];void add(int x,int y,int v){to[++tot]=y;val[tot]=v;next[tot]=head[x];head[x]=tot;}void dfs1(int x,int pre){int i,y;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre&&vis[y]==0){size[x]++;dfs1(y,x);sum[x]+=(size[y]?sum[y]/size[y]:0)+val[i];}}}void dfs2(int x,int pre){int i,y;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre&&vis[y]==0){if(fa[x])fa[y]=(sum[x]+fa[x]-(size[y]?sum[y]/size[y]:0)-val[i])/(size[x]+vis[x])+val[i];else{if(size[x]==1)fa[y]=val[i];elsefa[y]=(sum[x]+fa[x]-(size[y]?sum[y]/size[y]:0)-val[i])/(size[x]-1)+val[i];}}}for(i=head[x];i;i=next[i]){if((y=to[i])!=pre&&vis[y]==0){dfs2(y,x);}}}bool dfs_cir(int x,int pre){int i,y;vis[x]=1;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre){if(vis[y]){st[++top]=y,st[++top]=x;return 1;}if(dfs_cir(y,x)){if(st[1]!=x){st[++top]=x;return 1;}elsereturn 0;}}}return 0;}double dfs_cir2(int x,int pre,int en){int i,y;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre&&vis[y]){if(y!=en)return (sum[x]+val[i]+dfs_cir2(y,x,en))/(size[x]+1);elsereturn size[x]?sum[x]/size[x]:0;}}}int main(){int n,m,i,j,k,x,y,v;double ans;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&v);add(x,y,v),add(y,x,v);}if(m==n-1){dfs1(1,0);dfs2(1,0);for(i=1,ans=0;i<=n;i++){if(fa[i]&&sum[i])ans+=(fa[i]+sum[i])/(size[i]+1);else if(fa[i])ans+=fa[i];elseans+=sum[i]/size[i];}ans/=n;printf("%.5lf",ans);}if(m==n){dfs_cir(1,0);memset(vis,0,sizeof(vis));for(i=1;i<=top;i++)vis[st[i]]=1;for(i=1;i<=top;i++)dfs1(st[i],0);for(j=1;j<=top;j++){x=st[j];for(i=head[x];i;i=next[i]){if(!vis[y=to[i]])continue;fa[x]+=dfs_cir2(y,x,x)+val[i];}}for(i=1;i<=top;i++)dfs2(st[i],0);for(i=1,ans=0;i<=n;i++){ans+=(fa[i]+sum[i])/(size[i]+(vis[i]?2:1));}ans/=n;printf("%.5lf",ans);}return 0;}
上一篇bzoj-4204 取球游戏下一篇bzoj-1188 分裂游戏
顶0踩0
我们可以冷静理智的给这些刺一一贴上标签:骄傲，自负，脆弱的自尊心，
