Bzoj 3036: 綠豆蛙的歸宿(期望)

2019-11-10 17:18:15

字體：大中小

供稿：網(wǎng)友

3036: 綠豆蛙的歸宿 Time Limit: 2 Sec Memory Limit: 128 MB Description 隨著新版百度空間的下線，Blog寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。給出一個(gè)有向無環(huán)的連通圖，起點(diǎn)為1終點(diǎn)為N，每條邊都有一個(gè)長(zhǎng)度。綠豆蛙從起點(diǎn)出發(fā)，走向終點(diǎn)。到達(dá)每一個(gè)頂點(diǎn)時(shí)，如果有K條離開該點(diǎn)的道路，綠豆蛙可以選擇任意一條道路離開該點(diǎn)，并且走向每條路的概率為 1/K 。現(xiàn)在綠豆蛙想知道，從起點(diǎn)走到終點(diǎn)的所經(jīng)過的路徑總長(zhǎng)度期望是多少？ Input 第一行: 兩個(gè)整數(shù) N M，代表圖中有N個(gè)點(diǎn)、M條邊第二行到第 1+M 行: 每行3個(gè)整數(shù) a b c，代表從a到b有一條長(zhǎng)度為c的有向邊 Output 從起點(diǎn)到終點(diǎn)路徑總長(zhǎng)度的期望值，四舍五入保留兩位小數(shù)。 Sample Input 4 4 1 2 1 1 3 2 2 3 3 3 4 4 Sample Output 7.00 HINT 對(duì)于100%的數(shù)據(jù) N<=100000，M<=2*N Source Poetize3

/*期望=概率*貢獻(xiàn).然后把貢獻(xiàn)停留在點(diǎn)上最后累加.*/#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];