Mam takie zadanie: https://codeforces.com/problemset/problem/839/C
Nie wiem czy dobrze rozumiem "Expected Value" ale wydaje mi się że jest to suma wszystkich dróg / ilość dróg, dlatego mam BFS który idzie sobie po grafie i jak natrafi na liść to dodaje swoją długość do sumy wszystkich dróg i 1 do ilości dróg.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define FOR(x, y, z) for (int z = x; z < y; z++)
#define FORD(x, y, z) for (int z = x; z > y; z--)
const int INF = 1e9 + 7;
void solve(){
int n;
cin >> n;
vector<vector<int>> graph(n+1);
int a, b;
FOR(0, n-1, i){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
double sum = 0, amount = 0;
unordered_set<int> seen;
vector<int> que, new_que;
que.push_back(1); seen.insert(1);
for(int len = 0; (int)que.size() > 0; len++){
FOR(0, (int)que.size(), i){
bool add_new_road = false;
for (int next : graph[que[i]]){
if (seen.count(next) == false){
new_que.push_back(next);
seen.insert(next);
add_new_road = true;
}
}
if (add_new_road == false){
sum += len;
amount++;
}
}
que = new_que;
new_que.clear();
}
cout << setprecision(6) << fixed << sum / amount << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
ale mój program nie przechodzi wszytskich testów, czy coś jest nie tak w moim kodzie czy źle rozumiem "Expected Value"?
EDIT:
W odpowiedźi jest DFS działający bardzo podobnie do mojego programu, co robię źle ?
https://codeforces.com/blog/entry/53815
Zadanie C "Journey"
EDIT:
Źle rozumiałem co to Expected Value a do tego przykłady testowe mnie zmyliły, np dla takiego grafu:
Eval (Expected value) to suma długości do synów / ilość synów, czyli najpierw trzeba obliczyć Eval dla 2 ((1 + 2) / 2 = 1.5) a dopiero poźniej dla 2 i 3 (które są synami 1) ((1.5 + 1) / 2 = 1.25
Mój progam liczył wszystkie ścieżki od korzenia do liścia i dawał ich średnią, ((2 + 3 + 1) / 3 = 2)