2878: [Noi2012]迷失游樂園
Time Limit: 10 Sec Memory Limit: 512 MBSec Special Judge
Submit: 319 Solved: 223
[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
HINT
Source
鳴謝Ljcc提供SPJ
分析本題發現m=n-1或m=n，且圖連通.
故圖為樹或環加外向樹
樹：
對節點x，考慮向下走和向上走兩種情況，期望分別為down[x]和up[x]
環加外向樹：
對環上每棵樹的down[]，同上
考慮環上節點的up[]，k^2大暴力硬算
非環節點的up[]，可由環上節點up[]求出,方法仍同上
PS：考慮“無路可走”時，期望=0.0
在本題中有vector的erase(q.begin(),q.begin()+k)函數用法(刪除[0,k)區間)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (100000+10)
#define MAXM (300000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
typedef long double ld;
int n,m,edge[MAXM],pre[MAXN]={0},next[MAXM]={0},weight[MAXM],size=0;
void addedge(int u,int v,int w){edge[++size]=v;weight[size]=w;next[size]=pre[u],pre[u]=size;}
void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,w);}
long double up[MAXN]={0.0},down[MAXN]={0.0};
int fa[MAXN]={0},son[MAXN]={0};
void dfs_down(int x)
{
Forp(x)
{
int v=edge[p];
if (v^fa[x])
{
fa[v]=x;son[x]++;
dfs_down(v);
down[x]+=(ld)(weight[p]+down[v]);
}
}
if (son[x]) down[x]/=(ld)son[x];
}
void dfs_up(int x)
{
ld sum=0.0;
Forp(x)
{
int v=edge[p];
if (v^fa[x])
{
sum+=(ld)weight[p]+down[v];
}
}
if (fa[x]) sum+=up[x];
Forp(x)
{
int v=edge[p];
if (v^fa[x])
{
up[v]=sum-(ld)weight[p]-down[v];
if ((son[x]-(!fa[x]))) up[v]/=(son[x]-(!fa[x]));
up[v]+=(ld)weight[p];
dfs_up(v);
}
}
}
bool b[MAXN]={0},b2=0;
vector q,q2;
void print()
{
/* cout<
