題目描述

Description

放假了，小Z覺得呆在家里特別無聊，于是決定一個人去游樂園玩。進入游樂園后，小Z看了看游樂園的地圖，發現可以將游樂園抽象成有n個景點、m條道路的無向連通圖，且該圖中至多有一個環（即m只可能等于n或者n-1）。小Z現在所在的大門也正好是一個景點。小Z不知道什么好玩，于是他決定，從當前位置出發，每次隨機去一個和當前景點有道路相連的景點，并且同一個景點不去兩次（包括起始景點）。貪玩的小Z會一直游玩，直到當前景點的相鄰景點都已經訪問過為止。小Z所有經過的景點按順序構成一條非重復路徑，他想知道這條路徑的期望長度是多少？小Z把游樂園的抽象地圖畫下來帶回了家，可是忘了標哪個點是大門，他只好假設每個景點都可能是大門（即每個景點作為起始點的概率是一樣的）。同時，他每次在選擇下一個景點時會等概率地隨機選擇一個還沒去過的相鄰景點。

Input

第一行是兩個整數n和m，分別表示景點數和道路數。 接下來行，每行三個整數Xi, Yi, Wi，分別表示第i條路徑的兩個景點為Xi, Yi，路徑長Wi。所有景點的編號從1至n，兩個景點之間至多只有一條道路。

Output

?共一行，包含一個實數，即路徑的期望長度，保留五位小數

Sample Input

4 3
1 2 3
2 3 1
3 4 4

Sample Output

6.00000

【樣例解釋】樣例數據中共有6條不同的路徑: 路徑 長度 概率
1–>4 8 1/4
2–>1 3 1/8
2–>4 5 1/8
3–>1 4 1/8
3–>4 4 1/8
4–>1 8 1/4
因此期望長度 = 8/4 + 3/8 + 5/8 + 4/8 + 4/8 + 8/4 = 6.00
【評分方法】本題沒有部分分，你程序的輸出只有和標準答案的差距不超過0.01時，才能獲得該測試點的滿分，否則不得分。
【數據規模和約定】對于100%的數據，1 <= Wi <= 100。 測試點編號 n m 備注
1 n=10 m = n-1 保證圖是鏈狀
2 n=100 只有節點1的度數大于2
3 n=1000 /
4 n=100000 /
5 n=100000 /
6 n=10 m = n /
7 n=100 環中節點個數<=5
8 n=1000 環中節點個數<=10
9 n=100000 環中節點個數<=15
10 n=100000 環中節點個數<=20

HINT

Source

分析

如果是樹的話，可以向上DP一次，再向下DP一次求出解。

up:f[u]=∑f[u.son]degree[u]?(u==root)down:f[u.son]=(f[u]?f[u.son]×degree[u]?1degree[u])÷degree[u]?1degree[u]+f[u.son]

對于基環樹，我們可以拆成一個森林和一個環，其中每棵樹的就是環上的點。
我們先從下往上DP，然后再在環上暴力更新環上點的答案，再從上往下更新一遍就好了。

代碼

#include<cstdio> #include<algorithm> #define MAXN 100000 using namespace std; int n,m,d[MAXN+10],bgcir,cir[MAXN+10],cnt; double f[MAXN+10],ans,ff[MAXN+10],g[MAXN+10]; bool vis[MAXN+10]; void Read(int &x){char c;while(c=getchar(),c!=EOF)if(c>='0'&&c<='9'){x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';ungetc(c,stdin);return;} } struct node{int v,wt;bool vis;node *next,*back; }*adj[MAXN+10],edge[MAXN*2+10],*ecnt=edge,*pre[MAXN+10]; inline void addedge(int u,int v,int wt){node *p=++ecnt;p->v=v;p->wt=wt;p->next=adj[u];adj[u]=p;p->vis=0;p=p->back=++ecnt;p->v=u;p->wt=wt;p->next=adj[v];adj[v]=p;p->vis=0;p->back=ecnt-1; } void read(){Read(n),Read(m);int i,u,v,wt;for(i=1;i<=m;i++){Read(u),Read(v),Read(wt);d[u]++,d[v]++;addedge(u,v,wt);} } void dfs(int u,int fa){for(node *p=adj[u];p;p=p->next){if(p->v!=fa&&!p->vis){dfs(p->v,u);f[u]+=f[p->v]+p->wt;}}if(fa){if(d[u]>1)f[u]/=d[u]-1;}else{if(d[u])f[u]/=d[u];} } void dfs2(int u,int fa){for(node *p=adj[u];p;p=p->next){if(p->v!=fa&&!p->vis){if(d[u]>1)f[p->v]=((f[u]-(f[p->v]+p->wt)/d[u])/(d[u]-1)*d[u]+p->wt)/d[p->v]+f[p->v]/d[p->v]*(d[p->v]-1);elsef[p->v]=1.0*p->wt/d[p->v]+f[p->v]/d[p->v]*(d[p->v]-1);dfs2(p->v,u);}} } void solve(){dfs(1,0);dfs2(1,0);for(int i=1;i<=n;i++)ans+=f[i];ans/=n; } void find_cir(int u){if(vis[u]){bgcir=u;return;}vis[u]=1;for(node *p=adj[u];p;p=p->next){if(!p->vis){p->back->vis=p->vis=1;pre[p->v]=p;find_cir(p->v);}} } void solve2(){find_cir(1);int i=bgcir,j;for(node *p=edge;p<=ecnt;p++)p->vis=0;do{cir[++cnt]=i;pre[i]->vis=pre[i]->back->vis=1;i=pre[i]->back->v;}while(i!=bgcir);for(i=1;i<=cnt;i++){cir[i+cnt]=cir[i];d[cir[i]]-=2;dfs(cir[i],0);d[cir[i]]+=2;}for(i=1;i<=cnt;i++){g[cir[i+cnt-1]]=f[cir[i+cnt-1]];for(j=i+cnt-2;j>i;j--)g[cir[j]]=(g[cir[j+1]]+pre[cir[j]]->wt)/(d[cir[j]]-1)+f[cir[j]]/(d[cir[j]]-1)*(d[cir[j]]-2);g[cir[i]]=(g[cir[i+1]]+pre[cir[i]]->wt)/d[cir[i]];g[cir[i+1]]=f[cir[i+1]];for(j=i+2;j<i+cnt;j++)g[cir[j]]=(g[cir[j-1]]+pre[cir[j-1]]->wt)/(d[cir[j]]-1)+f[cir[j]]/(d[cir[j]]-1)*(d[cir[j]]-2);g[cir[i]]+=(g[cir[i+cnt-1]]+pre[cir[i+cnt-1]]->wt)/d[cir[i]];ff[cir[i]]=g[cir[i]]+f[cir[i]]/d[cir[i]]*(d[cir[i]]-2);}for(i=1;i<=cnt;i++){f[cir[i]]=ff[cir[i]];dfs2(cir[i],0);}for(i=1;i<=n;i++){ans+=f[i];}ans/=n; } int main() {read();if(m==n-1)solve();elsesolve2();printf("%.5lf\n",ans); }

轉載于:https://www.cnblogs.com/outerform/p/5921808.html

總結

以上是生活随笔為你收集整理的【基环树DP】[NOI2012]迷失游乐园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。