| 记录编号 |
167695 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2012]迷失游乐园 |
最终得分 |
100 |
| 用户昵称 |
 真呆菌 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.316 s |
| 提交时间 |
2015-06-27 20:16:38 |
内存使用 |
5.80 MiB |
显示代码纯文本
#include<cstdio>
using namespace std;
const int N = 100010;
typedef double fl;
template <class T> void R(T &x){
x=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
return;
}
int n,m,tot;
int to[N<<1],next[N<<1],head[N],val[N<<1],deg[N],fa[N],tw[N];
fl fd[N],fu[N];//向下走的期望 向上走的期望
void Add(int u,int v,int w){
to[++tot]=v;next[tot]=head[u];head[u]=tot;val[tot]=w;
}
namespace Subtask1{
int root,q[N],pf[N];//pf代表连向父亲的边的编号
int Siz(int x){return deg[x]-(x!=root);}//儿子节点的个数
void FD(){//向下走
int l=1,r=0,k;
q[++r]=root;fa[root]=root;
while(l<=r){
k=q[l++];
for(int i=head[k];i;i=next[i]){
if(!fa[to[i]]){
fa[to[i]]=k;pf[to[i]]=i;
q[++r]=to[i];
}
}
}
fa[root]=0;
for(int i=r;i>=1;i--){
k=q[i];
if(deg[k]>1){
fd[k]+=(fl)tw[k]-(fl)val[pf[k]];//tw是所有与该点相连的边的权值和
fd[k]/=(fl)Siz(k);//f[k]=sum(f[son[k]]+val[pf[son[k]]])/siz[k]
}
if(fa[k])fd[fa[k]]+=fd[k];
}
}
void FU(){
int k;
for(int i=2;i<=n;i++){
k=q[i];
fu[k]=(fl)val[pf[k]]+(Siz(fa[k])*fd[fa[k]]+fu[fa[k]]-fd[k]-(fl)val[pf[k]])/(Siz(fa[k])-(fa[k]==root));
}
//siz[fa[k]]*fd[fa[k]]是fa[k]向下走的所有期望
//减去(fd[k]+val[pf[k]]) 相当于到达除k的其他节点的期望
//再加上fa[k]向上走的期望 / (deg[fa[k]]-1) 是指到达除k的其他点的概率
//最后加上连向父亲的边
return;
}
void Work(){
for(int i=1;i<=n;i++) if(deg[i]!=1) {root=i;break;}
FD();FU();
fl res=0.0;
for(int i=1;i<=n;i++)
res+=(Siz(i)*fd[i]+fu[i])/(fl)deg[i];
res/=(fl)n;
printf("%.5lf\n",res);
return;
}
}
namespace Subtask2{
//在基环上每个点搞出down
//up和down求法与树上求法一样
//环上的点和与环直接相连的点处理有些不同
//环上考虑顺逆两种方向走
//与环上直接相连的点从父亲的走法多了一种（有两种走的方向了）
//写这个环套树DP真累啊QAQ
bool vis[N];
int rec,nn,siz[N],ff[N],sta[101],ss[101];
fl res=0.0;
int Next(int x){if(x==0) return nn;if(x==nn+1) return 1;return x;}
void RC(){
ss[0]=0;int k,pre=0;
ss[++ss[0]]=sta[1];
while(ss[0]!=nn){
k=ss[ss[0]];
for(int i=head[k];i;i=next[i]){
if(vis[to[i]]&&to[i]!=pre){
ss[++ss[0]]=to[i];
pre=k;
break;
}
}
}
return;
}
bool FC(int x,int fa){
if(vis[x]==1) {rec=fa;return 1;}
vis[x]=1;
for(int i=head[x];i;i=next[i])
if(to[i]!=fa&&FC(to[i],x)) return 1;
vis[x]=0;
return 0;
}
void FD(int x){
for(int i=head[x];i;i=next[i]){
if(vis[to[i]]||fa[to[i]]) continue;
fa[to[i]]=x;
FD(to[i]);
siz[x]++;
fd[x]+=fd[to[i]]+(fl)val[i];
}
if(siz[x]) fd[x]/=siz[x];
return;
}
void FU(int x,fl va){
int f=fa[x];
fu[x]=va+(ff[f]*fu[f]+siz[f]*fd[f]-va-fd[x])/(fl)(siz[f]-1+ff[f]);
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x]) FU(to[i],(fl)val[i]);
return;
}
void Work(){
FC(1,0);for(int i=1;i<=n;i++) vis[i]=0;
FC(rec,0);
for(int i=1;i<=n;i++)
if(vis[i]) sta[++nn]=i,ff[i]=2;
else ff[i]=1;
for(int i=1;i<=nn;i++) FD(sta[i]);
RC();
for(int nex,pre,ii,now,i=1;i<=nn;i++){
now=ss[i];
fl p=1.0;
for(int ii=Next(i+1);ii!=i;ii=Next(ii+1)){
nex=ss[ii];
pre=ss[Next(ii-1)];
if(Next(ii+1)==i){
for(int j=head[nex];j;j=next[j])
if(to[j]==pre)
fu[now]+=p*((fl)val[j]+fd[nex]);
}
else{
for(int j=head[nex];j;j=next[j])
if(to[j]==pre)
fu[now]+=p*((fl)val[j]+fd[nex]*siz[nex]/(siz[nex]+1));
}
p/=(fl)siz[nex]+1;
}
p=1.0;
for(int ii=Next(i-1);ii!=i;ii=Next(ii-1)){
nex=ss[ii];
pre=ss[Next(ii+1)];
if(Next(ii-1)==i){
for(int j=head[nex];j;j=next[j])
if(to[j]==pre)
fu[now]+=p*((fl)val[j]+fd[nex]);
}
else{
for(int j=head[nex];j;j=next[j])
if(to[j]==pre)
fu[now]+=p*((fl)val[j]+fd[nex]*siz[nex]/(siz[nex]+1));
}
p/=(fl)siz[nex]+1;
}
fu[now]/=2.0;
}
for(int i=1;i<=nn;i++)
for(int j=head[sta[i]];j;j=next[j])
if(!vis[to[j]]) FU(to[j],(fl)val[j]);
for(int i=1;i<=n;i++)
res+=(fd[i]*siz[i]+fu[i]*ff[i])/(fl)(ff[i]+siz[i]);
res/=(fl)n;
printf("%.5lf\n",res);
return;
}
}
int main(){
#define READ
#ifdef READ
freopen("noi2012_park.in","r",stdin);
freopen("noi2012_park.out","w",stdout);
#endif
using namespace Subtask1;
using namespace Subtask2;
R(n),R(m);
for(int u,v,w,i=1;i<=m;i++)
R(u),R(v),R(w),Add(u,v,w),Add(v,u,w),
deg[u]++,deg[v]++,tw[u]+=w,tw[v]+=w;
if(m==n-1) Subtask1::Work();
else Subtask2::Work();
return 0;
}