暴力不难想到,直接莽就可了
注意,dfs不要写全局变量
考试的时候因为这个挂了QAQ
55pts的code就不放了,太丑了
正解应该是dp或者记忆化搜索
然后,我还没改出来QAQ
好吧,改完了
他们说,这个记忆化搜索也是dpQAQ
设\(dp[i][j][0,1]\)分别表示男和女,在到第i个点,剩余体力为j时当前开心度的期望,然后我懒,用了个结构体,只写了一个dfs
在dfs一开始的时候,先判断这个状态之前是否到达过,如果之前到达过,直接返回这个值就可以了
然后其他的就跟普通dfs差不多了,直接放代码吧
Code:
#include<cstdio>
#define MAX 101
#define re register
namespace OMA
{
struct node
{
int next;
int to;
int w;
}edge[MAX*MAX];
struct data
{ double p1,p2; };
int cnt=1,head[MAX];
double ans1,ans2;
double dp[MAX][MAX*7][2];
int c[MAX],h1[MAX],h2[MAX];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline void add(int u,int v,int w)
{
edge[++cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
}
inline data dfs(int u,int k)
{
if(dp[u][k][0]||dp[u][k][1])
{ return (data){dp[u][k][0],dp[u][k][1]}; }
data ans;
ans.p1=h1[u],ans.p2=h2[u];
int du=0,to[MAX],w[MAX];
for(re int i=head[u]; i; i=edge[i].next)
{
int v=edge[i].to;
int t=edge[i].w;
if(k-t-c[v]>=0)
{ to[++du]=v,w[du]=t; }
}
if(!du)
{ return ans; }
for(re int i=1; i<=du; i++)
{
data temp=dfs(to[i],k-w[i]-c[to[i]]);
ans.p1+=temp.p1/du,ans.p2+=temp.p2/du;
}
dp[u][k][0]=ans.p1,dp[u][k][1]=ans.p2;
return ans;
}
signed main()
{
int n=read(),m=read(),k=read();
for(re int i=1; i<=n; i++)
{ c[i]=read(),h1[i]=read(),h2[i]=read(); }
for(re int i=1; i<=m; i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
for(re int i=1; i<=n; i++)
{
data temp=dfs(i,k-c[i]);
ans1+=(double)temp.p1,ans2+=(double)temp.p2;
}
printf("%.5lf %.5lf\n",ans1/n,ans2/n);
return 0;
}
}
signed main()
{ return OMA::main(); }