2878: [Noi2012]迷失遊樂園
Time Limit: 10 Sec Memory Limit: 512 MBSec Special Judge
Submit: 338 Solved: 238
[ Submit][ Status]
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.00000000
【樣例解釋】樣例資料中共有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
這題真不錯，被他折磨了好久~先看是顆樹的情況，用DOWN和UP分别表示從目前節點向下和向上走的期望長度，則有
DOWN[I]=SIGMA{(DIS[I,J]+DOWN[J])/totson[i]};
UP[i]:=DIS[I,J]+(down[j]*totson[j]-(down[i]+dis[i,j])+up[j])/totson[j];
O(N)可以求出所有的UP DOWN，然後計算統計平均值就行了。
然後是環套樹的情況，考慮到隻有一個環，且環上點的數量很少，可以把環單獨拿出處理，先以每個環上的點為根
求一遍DOWN,然後用O（N^2）的複雜度求出環上每個點的UP值，最後再更新所有樹上點的UP值，具體做法有很多種，
我是從每個環上點出發分别求出從左右兩個方向的期望長度，最後求出所有的UP和DOWN之後用相同方法求出平均值就行了，
雖然并不難想但處理起來細節還是很多的，很多時候根和環上點都要特殊處理，破壞了整體的美感。。。