题意

对于 n 个时间段中的每一个时间段 i,都有两门内容相同的课程分别在 c_id_i 教室上课,一开始被默认分到 c_i 上课,对于每个时间段 i 可以提交一个申请将教室从 c_i 换到 d_i,申请通过的概率为 k_i,一共可以提交 m 个申请。整个学校是一张无向图,求上课需要在教室间穿梭的期望最短路。

思路

期望 dp,考虑设计状态。注意到我们可以考虑当前上到了第 i 门课,提交了 j 份申请。然而发现对于某个 i,是否提交换教室的申请具有后效性,因此定义 f_{i,j,k}k\in\lbrace0,1\rbrace)来表示当前在第 i 个时间段提交了 j 份申请,第 i 个时间段的教室有没有提交申请的期望最短路值。

考虑转移:如果这节课不提交申请,那么问题就变得简单:

f_{i,j,0}=\min(f_{i-1,j,0}+dis_{c_{i-1},c_i},f_{i-1,j,1}+dis_{d_{i-1},c_i}\cdot k_{i-1}+dis_{c_{i-1},c_i}\cdot(1-k_{i-1}))

这个方程的意思就是考虑从前一个教室转移过来的情况,由于前一个换教室的申请有 k_{i-1} 的概率通过,但是也有 1-k_{i-1} 的概率不通过,所以为 f_{i-1,j,1}+dis_{d_{i-1},c_i}\cdot k_{i-1}+dis_{c_{i-1},c_i}\cdot(1-k_{i-1})

对于提交申请,就需要分六种情况讨论,如果从 f_{i-1,j-1,1} 转移来,则:

  • 这节课和上节课都通过了:期望加上 dis_{d_{i-1},d_i}\cdot k_i\cdot k_{i-1}(乘法原理)
  • 这节课通过了,上节课没通过:dis_{c_{i-1},d_i}\cdot k_i\cdot (1-k_{i-1})
  • 这节课没通过,上节课通过了:dis_{d_{i-1},c_{i}}\cdot (1-k_i)\cdot k_i
  • 这节课和上节课都没通过:dis_{c_{i-1},c_{i}}\cdot(1-k_i)\cdot(1-k_{i-1})

如果从 f_{i-1,j-1,0} 转移来,则只需考虑这节课的申请通不通过,就是

f_{i-1,j-1,0}+dis_{c_{i-1},d_i}\cdot k_i+dis_{c_{i-1},c_i}\cdot (1-k_i)

所以总的方程式就为:

for(int i=2;i<=n;++i)
    {
        f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
        for(int j=1;j<=m;++j)
        {
            f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],
                            f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]));
            if(j)
                f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][c[i]]*(1-k[i])+dis[c[i-1]][d[i]]*k[i],
                                f[i-1][j-1][1]+
                                dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+
                                dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+
                                dis[d[i-1]][c[i]]*k[i-1]*(1-k[i])+
                                dis[d[i-1]][d[i]]*k[i-1]*k[i]);
        }
    }

实现

坑点:

  • 图里面有重边和自环,要特判
  • 由于同一个教室里面不需要走路,所以 dis_{i,i} 的初值要设为 0
  • double 类型进行 memset 初始化时要用 127
  • 统计答案时,由于申请可以一条都不提交,所以答案为 \displaystyle\min_{i\in[0,m],k\in\lbrace 0,1\rbrace}\lbrace f_{n,i,k} \rbrace
#include <cstdio>
#include <cstring>

const int maxv=305,maxn=2005;
int n,m,v,e;
int c[maxn],d[maxn];
double k[maxn],f[maxn][maxn][2];
int dis[maxv][maxv];

template<typename T>inline T min(T a,T b){return a<b?a:b;}

int main()
{
    scanf("%d %d %d %d",&n,&m,&v,&e);
    for(int i=1;i<=n;++i)
        scanf("%d",c+i);
    for(int i=1;i<=n;++i)
        scanf("%d",d+i);
    for(int i=1;i<=n;++i)
        scanf("%lf",k+i);
    memset(dis,0x3f,sizeof dis);
    while(e--)
    {
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        dis[a][b]=dis[b][a]=min(dis[a][b],w);
    }
    for(int i=1;i<=v;++i)
        dis[i][i]=0;
    for(int r=1;r<=v;r++)
        for(int p=1;p<=v;p++)
            for(int q=1;q<=v;q++)
                dis[p][q]=min(dis[p][q],dis[p][r]+dis[r][q]);
    memset(f,127,sizeof f);
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;++i)
    {
        f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
        for(int j=1;j<=m;++j)
        {
            f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],
                            f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]));
            if(j)
                f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][c[i]]*(1-k[i])+dis[c[i-1]][d[i]]*k[i],
                                f[i-1][j-1][1]+
                                dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+
                                dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+
                                dis[d[i-1]][c[i]]*k[i-1]*(1-k[i])+
                                dis[d[i-1]][d[i]]*k[i-1]*k[i]);
        }
    }
    double ans=1e18;
    for(int i=0;i<=m;i++)
        ans=min(ans,min(f[n][i][0],f[n][i][1]));
    printf("%.2lf\n",ans);
    return 0;
}
最后修改日期:2020年11月24日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。