●Joyoi 绿豆蛙的归宿

题链：

http://www.joyoi.cn/problem/tyvj-1933
题解：

期望dp，拓扑序
定义dp[i]表示从i点到N点的期望距离。
令cnt[u]表示u的出度。
显然$$dp[u]=\sum_{u->v}(dp[v]+e(边权))* \frac{1}{cnt[u]}$$
由于是个DAG，所以拓扑排序后，从后向前dp即可。

题外话：为何不能正向dp：（希望聪明可爱的泥萌能看懂接下来的分析）

好吧，其实正向dp是可以的，但是没有反向dp来的直接和简单。
我们来看看弱弱的我当初觉得应该怎样去正向dp：
定义dp[i]表示从1点到i点的期望距离。
那么我们仿照之前反向dp的思路，我们找到当前v点的来源点u，
显然dp[v]肯定和dp[u]以及u的信息有关。
那u对v的贡献是不是就直接是$$dp[v]+=\frac{dp[u]+e(边权)}{cnt[u]}$$
即我们希望上式得到：
1到v的期望距离dp[v] = (1到u的期望距离 + u到v的边权)*(u到v的概率) [u为所有能到v的点]
为检验是否正确，我就试了几个小例子：

1.一个点没有边，答案为0，正确诶！（...）

2.两个点，一条边：1→ 2:3(箭头两头为边的起点和终点，3为边权)，答案为3，又正确了！（废话）

3.三个点，3条边：1→ 2:1，1→ 3:3，2→ 3:2，用脚趾头也算得出来答案为3，可是程序喜闻乐见地输出了一个4。

？？？怎么回事，dp哪里出现的问题？

经过一番分析，我找到了问题的根源，就处在dp转移时加的边权e那里。

在详细说明问题之前，我们先来看看通常倒着做的期望dp里面的各个状态的期望是如何实现递推的，
即一个状态j的期望是如何通过计算的到其前继状态i的期望的。
假设状态i转移到状态j的概率为p,代价为w，
用E(j)表示从状态j到结束的期望，E(i)表示从状态i到结束的期望，E(i→ j)表示状态i下一步必须为状态j，再到结束的期望。
由期望的定义可以知道：
E(j)=p1*w1+p2*w2+p3*w3+...+pn*wn(即第一种情况的概率*权值+第二种情况的概率*权值+...)
然后如果钦定i状态必须转移到j的话(代价为w)，不那发现，
E(i→ j)=p1*(w1+w)+p2*(w2+w)+p3*(w3+w)+...+pn*(wn+w)
注意到了么，从i→ j这个状态到结束的情况数没有变化，每种情况的概率也没变，唯一的变化只是每种情况的权值都加了w。
而通常倒着做的dp，我们定义的状态往往是表示从该状态出发到结束的期望，即把该状态看成了子问题的起点。
所以E(j)中所有的概率之和p1+p2+p3+...+pn = 1
那么：E(i→ j)=p1*(w1+w)+p2*(w2+w)+p3*(w3+w)+...+pn*(wn+w)
=p1*w1+p2*w2+p3*w3+...+pn*wn + p1*w+p2*w+p3*w+..+pn*w
=E(j)+w
然后再把这个所谓的"钦定"改为"有p的概率从状态i到状态j",并累加进E(i):
E(i)+=p*E(i→ j)即E(i)+=p*(E(j)+w)
本题我们反向dp的转移就是这么推出来的。

那么回到之前的问题，为何那样正向dp就出错了：
同样地，我们设当前在i点，其前继状态为j点，从j转移到i有p的概率，代价为w，
用E(j)表示从起点到j点的期望距离，E(i)表示从起点到i点的期望距离，E(j→ i)表示i点由j点而来的情况下，从起点到i点的期望距离。
我们用期望定义来写出E(j)的构成：
E(j)=p1*w1+p2*w2+p2*w3+...+pn*wn
然后类似上面的步骤，我们钦定i状态必须由j状态转移而来：
E(j→ i)=p1*(w1+w)+p2*(w2+w)+p3*(w3+w)+...+pn*(wn+w)
当然这里还没有任何问题，同样的是情况数没有变化，每种情况的概率也没变，唯一的变化只是每种情况的权值都加了w。
我们继续，尝试化简E(j→ i):
E(j→ i)=p1*(w1+w)+p2*(w2+w)+p3*(w3+w)+...+pn*(wn+w)
=p1*w1+p2*w2+p3*w3+...+pn*wn + p1*w+p2*w+p3*w+..+pn*w
=E(j)+p1*w+p2*w+p3*w+..+pn*w
然后上式等于E(j)+w么？
问题就出在这里。
当然不，因为这个dp定义下，每个dp状态的起点都是1号点，也就是说，
E(j)里面每种情况的概率应该是：第一种从1点到j的情况的概率p1，第二种从1点到j点的情况的概率p2，第三种p3...pn
但是显然1点不会只到j点，（好吧除了之前搞笑用的第一组和第二组测试数据）
所以g(j) = p1+p2+p3+...+pn ≠ 1，
那么顺理成章地可以得到 E(j→ i) ≠ E(j) + w
也就可以得到，没有所谓的"钦定"而是换成概率p，E(i)也不能加上p*(E(j)+w)，
所以正向dp错就错在$dp[v]+=\frac{dp[u]+e(边权)}{cnt[u]}$加的那个"dp[u]+e"，

至于我之前说的正向dp也可以正确，泥萌应该也有点思路了吧：
因为构成来源状态的期望值的那些概率的和g(j)不等于1，所以不能直接加上权值w，
那么我们就在dp的同时维护出从起点到每个状态的概率g，
然后再看上面的E(j→ i) = E(j)+p1*w+p2*w+p3*w+..+pn*w = E(j) + g(j)*w
也就是说dp本题正向dp的转移写成$dp[v]+=\frac{dp[u]+g[u]*e(边权)}{cnt[u]}$就完成没问题啦。
（实测AC，代码在下面的注释部分）

啰啰嗦嗦地说了1mol，希望对泥萌在理解正向和反向进行期望dp方面能有所帮助。

代码：

#include<bits/stdc++.h>

#define MAXN 100005

using namespace std;

struct Edge{

	int ent;

	int to[MAXN*2],val[MAXN*2],nxt[MAXN*2],head[MAXN];

	Edge():ent(2){}

	void Adde(int u,int v,int w){

		to[ent]=v; val[ent]=w;

		nxt[ent]=head[u]; head[u]=ent++;

	}

}E,F;

double dp[MAXN];

int order[MAXN],in[MAXN],cnt[MAXN];

int N,M,ont;

void bfs(){

	static queue<int>Q;

	Q.push(1);

	while(!Q.empty()){

		int u=Q.front(); Q.pop();

		order[++ont]=u;

		for(int e=E.head[u];e;e=E.nxt[e]){

			int v=E.to[e];

			in[v]--; if(!in[v]) Q.push(v);

		}

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin>>N>>M;

	for(int i=1,u,v,w;i<=M;i++)

		cin>>u>>v>>w,E.Adde(u,v,w),in[v]++,cnt[u]++,F.Adde(v,u,w);

	bfs();

	for(int i=N-1;i>=1;i--){

		int u=order[i];

		for(int e=E.head[u];e;e=E.nxt[e]){

			int v=E.to[e];

			dp[u]+=(dp[v]+E.val[e])/cnt[u];

		}

	}

	cout<<fixed<<setprecision(2)<<dp[1]<<endl;

	/*正推

	static double g[MAXN]; g[1]=1;

	for(int i=2;i<=N;i++){

		int u=order[i];

		for(int e=F.head[u];e;e=F.nxt[e]){

			int v=F.to[e];

			dp[u]+=(dp[v]+g[v]*F.val[e])/cnt[v];

			g[u]+=g[v]/cnt[v];

		}

	}

	cout<<fixed<<setprecision(2)<<dp[N]<<endl;

	*/

	return 0;

}

巴特西

●Joyoi 绿豆蛙的归宿

最新文章

热门文章