3036: 綠豆蛙的歸宿 Time Limit: 2 Sec Memory Limit: 128 MB Description 隨著新版百度空間的下線，Blog寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。 給出一個有向無環(huán)的連通圖，起點為1終點為N，每條邊都有一個長度。綠豆蛙從起點出發(fā)，走向終點。 到達每一個頂點時，如果有K條離開該點的道路，綠豆蛙可以選擇任意一條道路離開該點，并且走向每條路的概率為 1/K 。 現(xiàn)在綠豆蛙想知道，從起點走到終點的所經(jīng)過的路徑總長度期望是多少？ Input 第一行: 兩個整數(shù) N M，代表圖中有N個點、M條邊 第二行到第 1+M 行: 每行3個整數(shù) a b c，代表從a到b有一條長度為c的有向邊 Output 從起點到終點路徑總長度的期望值，四舍五入保留兩位小數(shù)。 Sample Input 4 4 1 2 1 1 3 2 2 3 3 3 4 4 Sample Output 7.00 HINT 對于100%的數(shù)據(jù) N<=100000，M<=2*N Source Poetize3
/*期望=概率*貢獻.然后把貢獻停留在點上最后累加.*/#include<cstdio>#define MAXN 100001using namespace std;int n,m,cut,tot,out[MAXN],head[MAXN];double s[MAXN],ans[MAXN],finalans;struct data{int v,next,x;}e[MAXN*2];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; }void add(int u,int v,int z){ e[++cut].v=v; e[cut].x=z; e[cut].next=head[u]; head[u]=cut;}void dfs(int u){ for(int i=head[u];i;i=e[i].next) { int v=e[i].v;s[v]=s[u]/out[u]; dfs(v); ans[u]+=s[v]*e[i].x; } return ;}int main(){ int x,y,z; n=read(),m=read(); while(m--) { x=read(),y=read(),z=read(); add(x,y,z),out[x]++; } s[1]=1; dfs(1); for(int i=1;i<=n;i++) finalans+=ans[i];新聞熱點
疑難解答
