【NOIP2018模拟赛2018.10.20】死宅与陷阱
题目
题解
–是一道典型的期望dp题
一个点的权值要对答案产生贡献,那么那条路径必须要经过它
所以我们反向建图(避免重复遍历),dp每个点经过它的概率
把概率最大的t的点追加陷阱(贪心),除了s
最后加起来就好了
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;
int n,m,p,s,t;
int head[MAXN],to[MAXN],next[MAXN],cnt;
double w[MAXN],d[MAXN],ans;
int v[MAXN],a[MAXN],du[MAXN];
void add(int u,int v,double l){
cnt++;
next[cnt]=head[u];
to[cnt]=v;
w[cnt]=l;
head[u]=cnt;
du[v]++;
}
double dfs(int x){
for(int i=head[x];i;i=next[i]){
int y=to[i];
if(d[y]!=0)
d[x]+=d[y]*w[i];
else
d[x]+=dfs(y)*w[i];
}
return d[x];
}
bool comp(const int &a,const int &b){
return d[a]>d[b];
}
int main(){
// freopen("trap.in","r",stdin);
// freopen("trap.out","w",stdout);
cin>>n>>m>>p>>s>>t;
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
a[i]=i;
}
for(int i=1;i<=m;i++){
int a,b;
double c;
scanf("%d%d%lf",&a,&b,&c);
add(b,a,c);
}
d[s]=1.00;
for(int i=1;i<=n;i++)
if(!du[i])
d[i]=dfs(i);
sort(a+1,a+1+n,comp);
for(int i=1;i<=t;i++)
v[a[i+1]]+=p;
for(int i=1;i<=n;i++)
ans+=d[i]*(double)v[i];
printf("%.3lf",ans);
return 0;
}