수학 적 기대 - 청개구리 의 귀착점 - 낙 곡 P4316

수학 적 기대 - 청개구리 의 귀착점 - 낙 곡 P4316
제목 설명
n 개의 점 m 변 의 방향 무 환 도 를 제시 합 니 다. 출발점 은 1 이 고 종점 은 n 입 니 다. 모든 변 은 길이 가 있 으 며 출발점 에서 출발 하여 모든 점 에 도착 할 수 있 고 모든 점 도 종점 에 도착 할 수 있 습 니 다.
녹두 개 구 리 는 출발점 에서 출발 하여 종점 으로 간다.모든 정점 에 도 착 했 을 때 이 노드 에 k 개의 가장자리 가 있 으 면 녹두 개 구 리 는 어느 한 쪽 을 선택 하여 이 점 을 떠 날 수 있 고 각 변 으로 갈 확률 은 1k \ frac {1} {k} k1 입 니 다.지금 녹두 개 구 리 는 출발점 에서 종점 까지 가 는 경로 의 총 길 이 를 얼마나 기대 하 는 지 알 고 싶 습 니 다.
입력 형식
입력 한 첫 줄 은 두 개의 정수 로 그림 의 포인트 n 과 변 수 m 를 대표 합 니 다.
2 번 부터 (m + 1) 줄 까지 줄 마다 세 개의 정수 u, v, w 가 있 는데 이것 은 u 에서 v 길 이 를 가리 키 는 w 의 방향 변 이 존재 한 다 는 것 을 의미한다.
출력 형식
한 줄 의 실 수 를 출력 하면 답 을 대표 하고 반올림 은 두 개의 소 수 를 보류한다.
입 출력 샘플
입력 \ # 1

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

출력 \ # 1

7.00

분석:
수학 적 기대: 이산 성 랜 덤 변수의 수학 적 기 대 는 실험 에서 매번 가능 한 결과 에 그 결과 확률 을 곱 하 는 총화 이다.이산 성 랜 덤 변수의 수학 적 기 대 는 실험 에서 매번 가능 한 결 과 를 그 결과 확률 의 총화 로 곱 하 는 것 이다.이산 성 랜 덤 변수의 수학 적 기 대 는 실험 에서 매번 가능 한 결 과 를 그 결과 확률 의 총화 로 곱 하 는 것 이다.
E ( x ) = ∑ w ∈ Ω X ( w ) P ( w ) E(x)=\sum_{w∈\Omega}X(w)P(w) E(x)=w∈Ω∑​X(w)P(w)
선형 성질:
① 、 E ( a X + b Y ) = a E ( X ) + b E ( Y ) ①、E(aX+bY)=aE(X)+bE(Y) ①、E(aX+bY)=aE(X)+bE(Y)
② 、 E ( X Y ) = E ( X ) E ( Y ) ②、E(XY)=E(X)E(Y) ②、E(XY)=E(X)E(Y)
본 문제:
기 f [i] 는 i 에서 종점 n 까지 의 기대 길 이 를 나타 낸다. 기 f [i] 는 i 에서 종점 n 까지 의 기대 길 이 를 나타 낸다. 기 f [i] 는 i 에서 종점 n 까지 의 기대 길 이 를 나타 낸다.
u 에서 j 까지 의 가능 한 결 과 는 f [u] + w u - > j 이 고 확률 은 1k 이 며 그 중에서 k 는 점 u 의 출 도 이다. u 에서 j 까지 의 가능 한 결 과 는 f [u] + w 이다.{u - > j}, 확률 은 \ frac {1} {k} 이 고 그 중에서 k 는 점 u 의 출 도 입 니 다. u 에서 j 까지 가능 한 결 과 는 f [u] + wu - > j 이 며 확률 은 k1 이 며 그 중에서 k 는 점 u 의 출 도 입 니 다.
f [j] = ∑ (f [u] + w u − > j)× 1 k 는 f [j] = \ sum (f [u] + w {u - > j})×\frac {1} {k} 은 f [j] = ∑ (f [u] + wu − > j)×k1​
종점 의 개 수 는 때때로 유일한 것 이 아니 기 때문에 우 리 는 습관 적 으로 종점 에서 기점 으로 반추 한다. 그러면 최종 답 은 f [1] 이다. 종점 의 개 수 는 때때로 유일한 것 이 아니 기 때문에 우 리 는 습관 적 으로 종점 에서 기점 으로 반추 한다. 그러면 최종 답 은 f [1] 이다. 종점 의 개 수 는 때때로 유일한 것 이 아니 기 때문에 우 리 는 습관 적 으로 종점 에서 기점 으로 반추 한다.이렇게 최종 답 은 f [1].
방법 1: 기억 화 검색
재 귀 실현 은 n 에 가 까 운 점 이 먼저 계산 되 고 재 귀 실현 은 n 에 가 까 운 점 이 먼저 계산 되 고 재 귀 실현 은 n 에 가 까 운 점 이 먼저 계산 된다.
거꾸로 밀 때 j 에서 u 로 가 는 것 과 같다. 즉 f [u] + = (w [i] + f [j])× 1 k, f [j] 는 재 귀 함수 에서 재 귀 계산 을 한 다음 에 되 돌아 갑 니 다. 역 추 시 는 j 에서 u, 즉 f [u] + = (w [i] + f [j]) 로 가 는 것 과 같 습 니 다.×\frac {1} {k}, f [j] 는 재 귀 함수 에서 재 귀 계산 을 하고 되 돌아 갑 니 다. 역 추 시 는 j 에서 u, 즉 f [u] + = (w [i] + f [j]) 로 가 는 것 과 같 습 니 다.×k1, f [j] 는 재 귀 함수 에서 먼저 재 귀 계산 한 다음 에 돌아간다.
방법 2: 토폴로지 그림 에서 DP
역방향 건축 도 는 n 에서 1 까지 토폴로지 순서 로 전달 하면 된다. 역방향 건축 도 는 n 에서 1 까지 토폴로지 순서 로 전달 하면 된다. 역방향 건축 도 는 n 에서 1 까지 토폴로지 순서 로 전달 하면 된다.
주의 하 세 요. 점 j 의 입 도 는 0 일 때 만 f [j] 가 완전히 계산 되 고 이때 만 점 j 를 팀 에 넣 을 수 있 습 니 다. 주의 하 세 요. 점 j 의 입 도 는 0 일 때 만 f [j] 가 완전히 계산 되 고 이때 만 점 j 를 팀 에 넣 을 수 있 습 니 다. 주의 하 세 요. 점 j 의 입 도 는 0 일 때 만 f [j] 가 다 계산 되 고 이때 만 점 j 를 팀 에 넣 을 수 있 습 니 다.
한편, 기억 화 검색 은 이 문 제 를 고려 할 필요 가 없다. j 에서 모든 인접 점 으로 확장 되 고 j 의 인접 점 의 기대 치 를 우선 계산 하기 때문이다. 기억 화 검색 은 이 문 제 를 고려 할 필요 가 없다. j 에서 모든 인접 점 으로 확장 되 고 j 의 인접 점 의 기대 치 를 우선 계산 하기 때문이다. 기억 화 검색 은 이 문 제 를 고려 할 필요 가 없다.j 에서 모든 인접 점 으로 확장 되 기 때문에 j 의 인접 점 의 기대 치 를 우선 계산 합 니 다.
기억 화 검색: 코드:

#include
#include
#include

using namespace std;

const int N=1e5+10, M=2*N;

int n,m;
int e[M],ne[M],w[M],h[N],idx;
double f[N];
int dout[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

double dp(int u)
{
    if(f[u]>=0) return f[u];
    f[u]=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        f[u]+=(w[i]+dp(j))/dout[u];
    }
    return f[u];
}

int main()
{
    scanf("%d%d",&n,&m);
    
    int a,b,c;
    memset(h,-1,sizeof h);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        dout[a]++;
    }
     
    memset(f,-1,sizeof f);
    
    printf("%.2lf
",dp(1));
    
    return 0;
}

토폴로지 순 DP 코드:

#include
#include
#include
#include

using namespace std;

const int N=1e5+10, M=2*N;

int n,m;
int e[M],ne[M],w[M],h[N],idx;
double f[N];
int dout[N], out[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

double dp(int u)
{   
    queue<int> Q;
    Q.push(n);
    f[n]=0;
    
    while(Q.size())
    {
        int u=Q.front();
        Q.pop();
        
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            f[j]+=(f[u]+w[i])/dout[j];
            out[j]--;
            if(!out[j]) Q.push(j);
        }
    }
    return f[1];
}

int main()
{
    scanf("%d%d",&n,&m);
    
    int a,b,c;
    memset(h,-1,sizeof h);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b,a,c);
        dout[a]++;
        out[a]++;
    }

    printf("%.2lf
",dp(1));
    
    return 0;
}