P1850 [NOIP2016] 换教室

P1850 [NOIP2016] 换教室

Meaning

给定一张有 $n$ 个点的无向图且有 $n$ 次事件。我们可以选择其中 $m$ 次事件作为特殊事件，有 $p_i$ 的概率从当前点去点 $ b_i $，否则去点 $ a_i $。求期望距离。

Sol

对于图上求多源最短路，注意到点数 $\leq 300$，跑 floyd 算法，时间复杂度为 $\text{O}(n^3)$。

然后我们考虑令 $dp_{i,j,0/1}$ 表示前 $i$ 次事件中选择了 $j$ 次事件，且上一次是否为特殊事件。那么就有转移方程

$dp_{i,j,0} = \min \{ dp_{i-1,j,0} + dis_{ a_{i-1} , a_{i} } , dp_{i-1,j,1} + p_{i-1} \times dis_{ b_{i-1} , a_{i} } + (1 - p_{i-1}) \times dis_{ a_{i-1} , a_{i} } \} \\ dp_{i,j,1} = \min \{ dp_{i-1,j-1,0} + p_{i} \times dis_{a_{i-1} , b_{i} } + (1 - p_{i}) \times dis_{ a_{i-1} , a_{i} } , dp_{i-1,j-1,1} + p_{i-1} \times ( p_{i} \times dis_{ b_{i-1} , b_{i} } + (1 - p_{i}) \times dis_{ b_{i-1} , a_{i} } ) + (1 - p_{i-1}) \times ( p_{i} \times dis_{ a_{i-1} , b_{i} } + (1 - p_{i}) \times dis_{ a_{i-1} , a_{i} } ) \}$

那么我们最终的答案即 $\min\{ dp_{n,i,0} ,dp_{n,i,1} \}$。

Detail

1. dp 转移方程写错了一开始没看出来，对于期望在 dp 里的应用不够深刻；
2. 其次忘记了图可能有重边；
3. floyd 求多源最短路时，应当先枚举中转站 $k$，再枚举最短路的两个端点。

Code

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e3+1e1,MAXM=3e2+1e1;
const lint INF=1e18+1e9;

double dp[MAXN][MAXN][2],dis[MAXM][MAXM],p[MAXM*MAXM],Ans=1e9;
int a[MAXN],b[MAXN],n,m,t,e;


int main(void){

	scanf("%d%d%d%d",&n,&m,&t,&e);
	for(int i=1;i<=t;i++) for(int j=1;j<=t;j++) dis[i][j]=1e9;
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j][0]=dp[i][j][1]=1e9;
	for(int i=1;i<=t;i++) dis[i][i]=dis[i][0]=dis[0][i]=0;
	for(int i=1;i<=n;i++) a[i]=readint;
	for(int i=1;i<=n;i++) b[i]=readint;
	for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
	for(int i=1;i<=e;i++){
		int u=readint,v=readint;
		dis[u][v]=dis[v][u]=min(dis[u][v],1.0*readint);
	}
	for(int k=1;k<=t;k++) for(int i=1;i<=t;i++) for(int j=1;j<=t;j++){
		dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
	}
	dp[1][0][0]=dp[1][1][1]=0.0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0]+1.0*dis[a[i-1]][a[i]];
		for(int j=1;j<=min(m,i);j++){
			dp[i][j][0]=min(dp[i-1][j][0]+1.0*dis[a[i-1]][a[i]],dp[i][j][0]);
			dp[i][j][0]=min(dp[i-1][j][1]+(1.0-p[i-1])*dis[a[i-1]][a[i]]+p[i-1]*dis[b[i-1]][a[i]],dp[i][j][0]);
			dp[i][j][1]=min(dp[i-1][j-1][0]+(1.0-p[i])*dis[a[i-1]][a[i]]+p[i]*dis[a[i-1]][b[i]],dp[i][j][1]);
			dp[i][j][1]=min(dp[i-1][j-1][1]+(1.0-p[i])*((1.0-p[i-1])*dis[a[i-1]][a[i]]+p[i-1]*dis[b[i-1]][a[i]])+p[i]*((1.0-p[i-1])*dis[a[i-1]][b[i]]+p[i-1]*dis[b[i-1]][b[i]]),dp[i][j][1]);
		}
	}
	for(int i=0;i<=m;i++) Ans=min(min(dp[n][i][0],dp[n][i][1]),Ans);
	printf("%.2lf\n",Ans);

	return 0;
}