【bzoj2878】 Noi2012—迷失游乐园

游乐园"/>

【bzoj2878】 Noi2012—迷失游乐园

.php?id=2878 (题目链接)

题意

　　求基环树上以任意点为起点的简单路径期望长度。

Solution

　　啊啊啊好丑陋。。

　　右转题解→_→：LCF

细节

　　注意特判环上最后一个点，以及算up的时候是否是根节点。

代码

// bzoj2878
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;const int maxn=100010;
int n,m,cnt,head[maxn],fa[maxn],dag[maxn],son[maxn],a[maxn];
double ans,up[maxn],down[maxn];
struct edge {int to,next,w;}e[maxn<<1];void link(int u,int v,int w) {e[++cnt]=(edge){v,head[u],w};head[u]=cnt;e[++cnt]=(edge){u,head[v],w};head[v]=cnt;
}
void topsort() {queue<int> q;for (int i=1;i<=n;i++) if (dag[i]==1) q.push(i);while (!q.empty()) {int x=q.front();q.pop();for (int i=head[x];i;i=e[i].next)if (dag[e[i].to]>1) if (--dag[e[i].to]==1) q.push(e[i].to);}
}namespace Tree {void dfs(int x) {for (int i=head[x];i;i=e[i].next) if (dag[e[i].to]==1 && fa[x]!=e[i].to) {fa[e[i].to]=x;dfs(e[i].to);down[x]+=down[e[i].to]+e[i].w;son[x]++;}if (son[x]) down[x]/=son[x];}void dfs(int x,int len) {if (fa[x]) up[x]=(down[fa[x]]*son[fa[x]]-down[x]-len+dag[fa[x]]*up[fa[x]])/(son[fa[x]]-1+dag[fa[x]])+len;for (int i=head[x];i;i=e[i].next)if (dag[e[i].to]==1 && e[i].to!=fa[x]) dfs(e[i].to,e[i].w);}void main() {dag[1]=0;dfs(1);dfs(1,0);for (int i=1;i<=n;i++)ans+=(up[i]+down[i]*son[i])/(son[i]+(fa[i]!=0));}
}
namespace Circle {int rt,t=0;double dfs(int x,int fa) {double sum=0;int flag=0;for (int i=head[x];i;i=e[i].next)if (e[i].to!=fa && dag[e[i].to]==2 && e[i].to!=rt) sum+=e[i].w+dfs(e[i].to,x),flag=1;return x==rt ? sum/2 : (son[x]+flag ? (sum+down[x]*son[x])/(son[x]+flag) : 0);}void main() {for (int i=1;i<=n;i++) if (dag[i]==2) Tree::dfs(i),a[++t]=i;for (int i=1;i<=t;i++) up[rt=a[i]]=dfs(a[i],0);for (int i=1;i<=t;i++) Tree::dfs(a[i],0);for (int i=1;i<=n;i++)ans+=(up[i]*dag[i]+down[i]*son[i])/(son[i]+dag[i]);}
}int main() {scanf("%d%d",&n,&m);for (int u,v,w,i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&w);link(u,v,w);dag[u]++,dag[v]++;}topsort();if (m==n-1) Tree::main();else Circle::main();printf("%.5lf",ans/n);return 0;
}

转载于:.html