| 记录编号 |
61486 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2012]迷失游乐园 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.970 s |
| 提交时间 |
2013-06-10 18:54:07 |
内存使用 |
173.39 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=200001;
int N,M;//总点数
vector<int> circle;//环上的点集
bool becir[SIZEN]={0};//点是否在环上
int liscir[SIZEN]={0};
double cirl[100][100]={0};
int numc;
int lencir=0;
int eff_tree=0;
class TREE{
public:
int n;//下标从1开始
int root;
vector<pair<int,int> > c[SIZEN];//邻接表
bool visit[SIZEN];
double ans[SIZEN],up[SIZEN],down[SIZEN];
int numson[SIZEN];
void clear();
bool DFS_cir(int,int,int);
void findcir();
void getdown(int,int);
void getup(int,int,int);
void DFS_ext(int,TREE&,int);
void extend();
double calc_ans();
};
TREE G;
TREE inc[21];
void TREE::clear(){
n=0;
int i;
for(i=0;i<=N;i++) visit[i]=false,ans[i]=up[i]=down[i]=numson[i]=0;
}
int low=0;
bool TREE::DFS_cir(int x,int father,int len){
if(visit[x]){//找到环了
circle.push_back(x);
becir[x]=true;
liscir[x]=circle.size();
low=x;
lencir+=len;
return true;
}
visit[x]=true;
int i;
bool flag;
for(i=0;i<c[x].size();i++){
if(c[x][i].first!=father){
flag=DFS_cir(c[x][i].first,x,c[x][i].second);
if(flag){
if(x!=low){
circle.push_back(x);
becir[x]=true;
liscir[x]=circle.size();
lencir+=len;
}
cirl[liscir[x]][liscir[c[x][i].first]]=cirl[liscir[c[x][i].first]][liscir[x]]=c[x][i].second;
return x!=low;
}
}
}
return false;
}
void TREE::findcir(void){
DFS_cir(root,0,0);
}
void TREE::getdown(int x,int father){//get down!!!!!
if(numson[x]==0){
down[x]=0;
return;
}
int i;
for(i=0;i<c[x].size();i++){
if(c[x][i].first!=father&&!becir[c[x][i].first]){
getdown(c[x][i].first,x);
down[x]+=double(c[x][i].second+down[c[x][i].first])/double(numson[x]);
}
}
}
void TREE::getup(int x,int father,int l){//好喜感的名字
if(becir[x]){
int i;
for(i=0;i<c[x].size();i++){
getup(c[x][i].first,x,c[x][i].second);
}
return;
}
up[x]+=l;
double temp;
double siz;
siz=c[father].size()-1;
temp=up[father]*(c[father].size()-numson[father])+down[father]*numson[father]-l-down[x];
if(siz>0) temp/=siz;
else temp=0;
up[x]+=temp;
int i;
for(i=0;i<c[x].size();i++){
if(c[x][i].first!=father){
getup(c[x][i].first,x,c[x][i].second);
}
}
}
void TREE::DFS_ext(int x,TREE &s,int father){
if(x!=s.root) s.numson[x]=c[x].size()-1;
else s.numson[x]=c[x].size()-2;
s.n++;
int i;
for(i=0;i<c[x].size();i++){
s.c[x].push_back(c[x][i]);
if(!becir[c[x][i].first]&&c[x][i].first!=father){
DFS_ext(c[x][i].first,s,x);
}
}
}
void TREE::extend(void){
int i,u;
for(i=0;i<circle.size();i++){
u=circle[i];
inc[liscir[u]].clear();
inc[liscir[u]].root=u;
DFS_ext(u,inc[liscir[u]],0);
if(inc[liscir[u]].n>1) eff_tree++;
}
numc=circle.size();
}
double TREE::calc_ans(void){
int i;
double sum=0;
for(i=1;i<=N;i++){
if(!c[i].size()) continue;
sum+=double(down[i]*numson[i]+up[i]*(c[i].size()-numson[i]))/double(c[i].size());
}
return sum/N;
}
void calc_cir(void){
int i,j;
double prob,len,lastpro;
double temp=0;
int now;
int jump;
for(i=1;i<=numc;i++){
prob=0.5;
len=0;
now=i;
for(j=1;j<numc;j++){
jump=now;
now++;
if(now>numc) now-=numc;
len+=cirl[jump][now];
if(inc[now].n>1){
lastpro=prob;
prob*=1.0/double(inc[now].c[inc[now].root].size()-1);
temp=len+inc[now].down[inc[now].root];
inc[i].up[inc[i].root]+=temp*(lastpro-prob);
}
}
if(inc[now].n==1){
inc[i].up[inc[i].root]+=prob*len;
}
else{
inc[i].up[inc[i].root]+=prob*(len+inc[now].down[inc[now].root]);
}
prob=0.5;
len=0;
now=i;
for(j=1;j<numc;j++){
jump=now;
now--;
if(now<1) now+=numc;
len+=cirl[jump][now];
if(inc[now].n>1){
lastpro=prob;
prob*=1.0/double(inc[now].c[inc[now].root].size()-1);
temp=len+inc[now].down[inc[now].root];
inc[i].up[inc[i].root]+=temp*(lastpro-prob);
}
}
if(inc[now].n==1){
inc[i].up[inc[i].root]+=prob*len;
}
else{
inc[i].up[inc[i].root]+=prob*(len+inc[now].down[inc[now].root]);
}
}
}
double answer(void){
if(N-1==M) return G.calc_ans();
int i;
double sum=0;
for(i=0;i<circle.size();i++){
sum+=inc[liscir[circle[i]]].calc_ans();
}
return sum;
}
void read(void){
G.clear();
scanf("%d%d",&N,&M);
G.root=1;
int i,x,y,w;
for(i=1;i<=M;i++){
scanf("%d%d%d",&x,&y,&w);
G.c[x].push_back(make_pair(y,w));
G.c[y].push_back(make_pair(x,w));
}
for(i=1;i<=N;i++){
if(i!=G.root) G.numson[i]=G.c[i].size()-1;
else G.numson[i]=G.c[i].size();
}
}
void work(void){
if(N-1==M){
G.getdown(G.root,0);
G.getup(G.root,0,0);
printf("%.5lf\n",answer());
return;
}
G.findcir();
G.extend();
int i;
for(i=1;i<=circle.size();i++) inc[i].getdown(inc[i].root,0);
calc_cir();
for(i=1;i<=circle.size();i++) inc[i].getup(inc[i].root,0,0);
printf("%.5lf\n",answer());
}
int main(){
freopen("noi2012_park.in","r",stdin);
freopen("noi2012_park.out","w",stdout);
read();
work();
return 0;
}