Menu Home

BZOJ3036: The Destiny of the LEON

Problem Description: There are N nodes and M directed roads with weight in an acyclic graph. At each node, there is a probability of 1 / K to go to each next node, where K number of roads that are connected to current node. Starting at 1, calculate the total expectancy distance to go to N. 

Input Format:

First line consists of two integers N ≤ 1000000, M ≤ 2N.

The next M lines consist of a,b,c, meaning a road from a to b weight/distance c.

Output Format:

One line with the answer, round the answer up to 0.01 in accuracy.

Sample Input:
1 2 1
1 3 2
2 3 3
3 4 4

Sample Output:

7.00

 

Solution: Emm, as hzwer said, easy problems are good for health. (JUST DO A DFS, and be careful with memory when doing dfs  T_T) .

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
vector<pii> G[maxn];
bool vis[maxn]
int N,M;
double f[maxn];

void dfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    int sz = G[u].size();
    for(int i = 0; i < sz; i++){
        dfs(G[u][i].first);
	f[u] += f[G[u][i].first] + G[u][i].second;
    }
    if(G[u].size()) f[u] /= (1.0 * sz)
}
int main(){
    FAST_IO
    cin>>N>>M;
    for(int i = 1; i <= M; i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back(pii(v,w));
    }
    dfs(1);
    cout<<fixed<<setprecision(1)<<ans<<endl;
    return 0;
}

 

Categories: OI BZOJ DFS Math Expectancy

appledorem

Leave a Reply

Your email address will not be published. Required fields are marked *