緑豆蛙の帰宿#
緑豆 WA の帰宿
問題#
問題背景#
新しいバージョンの百度スペースの立ち上げに伴い、Blog ペットの緑豆蛙はその使命を果たし、新しい帰宿を探しに行きました。
問題の説明#
有向非巡回グラフが与えられ、始点は 1、終点は N です。各辺には長さがあり、始点からすべての点に到達でき、すべての点も終点に到達できます。緑豆蛙は始点から出発し、終点に向かいます。 各頂点に到達するたびに、K 本の出発する道路がある場合、緑豆蛙はその点から出発する任意の道路を選択でき、各道路を選ぶ確率は 1/K です。 さて、緑豆蛙は始点から終点に至るまでの経路の総長さの期待値がいくらになるかを知りたいと思っています。
入力出力形式#
入力形式：#
1 行目: 2 つの整数 N M、グラフに N 個の点と M 本の辺があることを示します。 2 行目から 1+M 行目まで：各行に 3 つの整数 a b c、a から b への長さ c の有向辺を示します。
出力形式：#
始点から終点までの経路の総長さの期待値を、小数点以下 2 桁に四捨五入して出力します。
入力出力サンプル#
入力サンプル #1：#
4 4
1 2 1
1 3 2
2 3 3
3 4 4
出力サンプル #1：#
7.00
説明#
20% のデータに対して N<=100
40% のデータに対して N<=1000
60% のデータに対して N<=10000
100% のデータに対して N<=100000、M<=2*N
分析#
DFS を用いて各経路を列挙します。
各交差点で確率を計算します。
終点に到達するために確率 * 経路長を計算します。
（大佬はみんなトポロジカルソートを使っていますが、私は DFS しかできません）
トポロジカルソートの方法については：
dyx 大佬のブログ
perisino 大佬のブログ
コード#
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005*2;
struct tu{
private:
struct ed{//連鎖前向き星を用いてグラフを保存
int to,nex,w;
} e[MAXN];
int head[MAXN],newp;
public:
tu(void){//初期化
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
}
void insert(int p1,int p2,int w){//挿入、前挿入
++newp;
e[newp].to=p2;
e[newp].nex=head[p1];
e[newp].w=w;
head[p1]=newp;
}
double solve(int s,int e){
return dfs(s,0,1,e);
}
double dfs(int p,int tot,double gl,int end){//現在の点、現在の長さ、現在の確率、終了点
double ret=0;
int cnt=0;
if(p==end){
//出口条件、確率*経路総長を返す
return tot*gl;
}
for(int i=head[p];i!=0;i=e[i].nex){
++cnt;
}//可能性をカウント
for(int i=head[p];i;i=e[i].nex){
ret+=dfs(e[i].to,tot+e[i].w,gl/cnt/* gl*(1/cnt) */,end);
}
return ret;//retは現在の点から終点までの期待確率
}
};
tu a;
int main(void){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int p1,p2,w;
scanf("%d%d%d",&p1,&p2,&w);
a.insert(p1,p2,w);
}
printf("%.2lf",a.solve(1,n));
return 0;
}