这是代码...
```cpp
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,m,x,y,z,tot=0,p=0,k=0;
int head[maxn],cir[maxn],son[maxn],fa[maxn],hash1[maxn],next[maxn],pre[maxn];
bool vis[maxn];
double down[maxn],up[maxn],len[100][100],ans=0;
struct node{int to,next;double w;} e[maxn*2];
void read(int &ans)
{
char x=getchar();ans=0;
while(x>'9' || x<'0') x=getchar();
while(x>='0' && x<='9') ans=ans*10+x-'0',x=getchar();
}
void add(int u,int v,double w)
{
e[++k].next=head[u],e[k].to=v,e[k].w=w,head[u]=k;
e[++k].next=head[v],e[k].to=u,e[k].w=w,head[v]=k;
}
void dfsdown(int u,int pre)
{
for(int i=head[u];i;i=e[i].next)
if(!vis[e[i].to] && e[i].to!=pre){
dfsdown(e[i].to,u);
son[u]++;fa[e[i].to]=1;
down[u]+=e[i].w+down[e[i].to];
}
if(son[u]) down[u]/=son[u];
}
void dfsup(int x,int f,double w)
{
up[x]=w;
if(son[f]-1+fa[f]>0) up[x]+=(son[f]*down[f]-down[x]-w+up[f]*fa[f])/(son[f]-1+fa[f]);
//printf("%d:%lf\n",x,up[x]);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=f) dfsup(e[i].to,x,e[i].w);
}
void findcir(int x,int pre)
{
vis[x]=true;
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=pre){
if(!vis[e[i].to]) findcir(e[i].to,x);
if(vis[e[i].to]) {p=e[i].to;return;}
if(p>0) {
if(p==x) p=-1;
return;
}
if(p==-1) break;
}
vis[x]=false;
}
void dfscir(int x,int pre1)
{
if(hash1[x]>0) return;
cir[++tot]=x;hash1[x]=tot;fa[x]=2;
for(int i=head[x];i;i=e[i].next)
if(vis[e[i].to] && e[i].to!=pre1){
next[x]=e[i].to;pre[e[i].to]=x;
dfscir(e[i].to,x);
len[hash1[x]][hash1[e[i].to]]=len[hash1[e[i].to]][hash1[x]]=e[i].w;
break;
}
}
void treat_cir()
{
for(int i=1;i<=tot;i++){
double p1=1;int x=cir[i];
for(int j=next[x];j!=x;j=next[j]){
if(next[j]!=x) up[x]+=p1*(len[hash1[pre[j]]][hash1[j]]+(son[j]*down[j])/(son[j]+1));
else up[x]+=p1*(len[hash1[pre[j]]][hash1[j]]+down[j]);
p1/=(son[j]+1);
}
p1=1;
for(int j=pre[x];j!=x;j=pre[j]){
if(pre[j]!=x) up[x]+=p1*(len[hash1[next[j]]][hash1[j]]+(son[j]*down[j])/(son[j]+1));
else up[x]+=p1*(len[hash1[next[j]]][hash1[j]]+down[j]);
p1/=(son[j]+1);
}
up[x]/=2;
//printf("%lf %lf\n",up[x],down[x]);
}
}
int main()
{
read(n);read(m);
for(int i=1;i<=m;i++){
read(x);read(y);read(z);
add(x,y,z);
}
if(n>m){
dfsdown(1,0);
for(int i=head[1];i;i=e[i].next)
dfsup(e[i].to,1,e[i].w);
}
else{
memset(vis,false,sizeof(vis));
memset(hash1,0,sizeof(hash1));
findcir(1,0);
for(int i=1;i<=n;i++) if(vis[i])
{dfscir(i,0);break;}
for(int i=1;i<=tot;i++) dfsdown(cir[i],0);
treat_cir();
for(int i=1;i<=tot;i++)
for(int j=head[cir[i]];j;j=e[j].next)
if(!hash1[e[j].to]) dfsup(e[j].to,cir[i],e[j].w);
}
for(int i=1;i<=n;i++) ans+=(son[i]*down[i]+up[i]*fa[i])/(son[i]+fa[i]);
printf("%.5lf\n",ans/n);
return 0;
}
```
/\*
9 9
1 2 2
1 3 3
3 5 5
2 4 4
4 6 3
6 8 2
6 9 3
5 7 4
4 5 2
\*/
by Memorize @ 2017-03-14 10:56:14
我把 next pre改了就行了.... 难道这是关键字?
by Memorize @ 2017-03-14 11:23:34
不要在意这些细节
by 徐卓然666 @ 2017-04-06 22:58:29
next就是关键字。。。。
by XiaoX @ 2018-07-07 09:30:45
所以把
```
using namespace std;
```
去掉就好了
by ddwqwq @ 2018-09-16 15:07:36