[概率期望DP] 2019 南京网络赛 D.Robot 绿豆蛙的归宿

绿豆蛙的归宿

https://www.luogu.org/problem/P4316
首先这道题 是在图上dp的一个标准板子题
一般意义上 我们需要每个点的转移方程 但是 这是一个图 所以我们考虑拓扑
同时 每个点连的边数也是需要考虑变成转移系数
这样就有了我们算法进阶指南书上 代码 很好理解
但是 如果当我们甚至 可以停留在原地 或者 有一定概率 直接回到过去的点 的时候 他的写法就不满足 我们更复杂的dp转移的
书上代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;

int n, m;
int head[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1], val[maxn << 1];

void ade(int a, int b, int c) {
	to[++ cnt] = b, val[cnt] = c;
	nxt[cnt] = head[a], head[a] = cnt;
}

int out[maxn], deg[maxn];
double dis[maxn];

void topsort() {
	queue<int> que;
	que.push(n);
	while(!que.empty()) {
		int x = que.front(); que.pop();
		for(int i = head[x]; i; i = nxt[i]) {
			int y = to[i];
			dis[y] += (dis[x] + 1.0 * val[i]) / deg[y];
			out[y] --;
			if(out[y] == 0) que.push(y);
		}
	}
}

signed main() {
	scanf("%d %d", &n, &m);
	for(int i = 1, a, b, c; i <= m; ++ i) {
		scanf("%d %d %d", &a, &b, &c);
		ade(b, a, c);
		out[a] ++, deg[a] ++;
	}
	topsort();
	printf("%.2lf\n", dis[1]);
	return 0;
}

以下 是我自己 按照理解写的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int head[maxn], cnt;
int to[maxn], nxt[maxn];
int from[maxn], pre[maxn], come[maxn], val[maxn], tot;
int out[maxn], deg[maxn];
double dis[maxn];

void cometo(int a, int b, int c) {
    come[++ tot] = b, val[tot] = c;
    pre[tot] = from[a],  from[a] = tot;
}

void ade(int a, int b) {
    to[++ cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

double redis(int u) {
    if(u == n) return 0;
    double res = 0;
    for(int i = from[u]; i; i = pre[i]) {
        res += (dis[come[i]] + 1.0 * val[i]) / deg[u];
    }
    return res;
}

void topsort() {
    queue<int> que;
    que.push(n);
    while(!que.empty()) {
        int x = que.front(); que.pop();
        dis[x] = redis(x);
        for(int i = head[x]; i; i = nxt[i]) {
            out[to[i]] --;
            if(out[to[i]] == 0) que.push(to[i]);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b, c; i <= m; ++ i) {
        scanf("%d %d %d", &a, &b, &c);
        cometo(a, b, c), ade(b, a);
        deg[a] ++, out[a] ++;
    }
    topsort();
    printf("%.2lf\n", dis[1]);
    return 0;
}

2019南京网络赛 D. Robot

首先是推公式了 如果你理解了上面的题 这个公式很简单推出
不过这里 我们天数是我们的消耗 每次走都是 不同的 所以我们先得求一个点天数期望
在去 算 损耗期望

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;

int n, m;
int head[maxn], cnt;
int to[maxn], nxt[maxn];

int pre[maxn], come[maxn], from[maxn], tot;
int out[maxn], deg[maxn], out2[maxn];
double dis[maxn], ans[maxn];

void cometo(int a, int b) {
    out[a] ++, out2[a] ++, deg[a] ++;
    pre[++ tot] = from[a], from[a] = tot, come[tot] = b;
}

void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

double redays(int u) {
    if(u == n) return 0;
    double res = 0;
    for(int i = from[u]; i; i = pre[i]) 
        res += dis[come[i]];
    return (res + deg[u] + 1) / deg[u];
}

void topsort1() {
	queue<int> que;
	que.push(n);
	while(!que.empty()) {
		int x = que.front(); que.pop();
        dis[x] = redays(x);
        for(int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            out[y] --;
            if(out[y] == 0) que.push(y);
        }
	}
}

double recon(int u) {
    if(u == n) return 0;
    double res = 0;
    for(int i = from[u]; i; i = pre[i]) 
        res += ans[come[i]] + dis[u];
    return (res + dis[u]) / deg[u];
}
queue<int> que;
void topsort2() {
	que.push(n);
	while(!que.empty()) {
		int x = que.front(); que.pop();
        ans[x] = recon(x);
        for(int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            out2[y] --;
            if(out2[y] == 0) que.push(y);
        }
	}
}

signed main() {
	int cas;
	scanf("%d" ,&cas);
	while(cas --) {
		scanf("%d %d", &n, &m);
		memset(head, 0, (n + 5) * sizeof(int));
        memset(dis, 0, (n + 5) * sizeof(int));
        memset(ans, 0, (n + 5) * sizeof(int));
        memset(out2, 0, (n + 5) * sizeof(int));
        memset(deg, 0, (n + 5) * sizeof(int));
        memset(from, 0, (n + 5) * sizeof(int));
		cnt = 0, tot = 0;
		for(int i = 1, a, b; i <= m; i ++) {
			scanf("%d %d", &a, &b);
			cometo(a, b), ade(b, a);
		}
		topsort1();
		topsort2();
		printf("%.2lf\n", ans[1]);
	}
	return 0;
}