tilian
期望dp
k=12
我们很可以推出dp状态为 t u state 转移则是一个 O（m）的转移
更加具体的 表示当前t时间我在u结点 并且state被占用的最大期望值
因为我们要算最大期望值 我们只care的是有记忆体的点 是否还有权值存在
所以这个state的含义就是 0/1 该点时候有权值存在的一个状态压缩
思考完状态 我们继续思考如何转移
我们知道起点 但是期望dp都是倒着进行的
我们知道dp[n][?][?]=0的
这样我们可以dfs 才用记忆化的方式就可以从结尾开始dp
具体转移有两种
这里w[v]表示的就是v点在状态压缩里的
因为我们该点是进行了一次走 再进行一次被污染
走肯定是枚举
被污染就有两种转移
一是我们污染的点 是占掉了我们没有get到的记忆体
cntw=未感染点个数=n-t
dp[t][u][s] <- dp[t+1][v][s|w[v]|w[没有get到的记忆体]] 概率为1/cntw
二是感染点 是占掉了无关点或者我们以前get到的点
dp[t][u][s] <- dp[t+1][v][s|w[v]] 概率为 1 - 第一种转移的概率之和
这样我们就完成了dp的转移
但是要注意的是 因为我们是倒着转移的所以有些转移要加一些条件
db dp[31][31][1<<12];//表示 当前i时间我在j结点 并且state被占用的最大期望值
// dp[u][t][s] <- dp[v][t+1][s|w[v]] w-cnt0/w
// dp[u][t][s] <- dp[v][t+1][s|w[v]|id[i]] 1/w
int n,m,k;
vector<int>g[31],w(31),id,c(31);
db dfs(int u,int t,int s){
if(t>n)return 0;
auto &V=dp[u][t][s];
if(V>=0)return V;
V=0;
for(auto v:g[u]){
int ns=w[v]|s,wq=n-t,cnt0=0;
db res=0;
for(int i=0;i<id.size();i++)
if(!(ns&w[id[i]]))res+=dfs(v,t+1,ns|w[id[i]])*1.0/wq,cnt0++;
res+=dfs(v,t+1,ns)*(wq-cnt0)/wq;
if(!(s&w[v]))res+=c[v];
V=max(V,res);
}
return V;
}
void solve(){
cin>>n>>m>>k;
memset(dp,-127,sizeof dp);
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int>a;
for(int i=0;i<k;i++){
int x;cin>>x;
c[x]++;
a.push_back(x);
}
sort(all(a));
a.erase(unique(all(a)),a.end());
for(int i=0;i<a.size();i++){
w[a[i]]=1<<i;
id.push_back(a[i]);
}
// for(int i=1;i<=n;i++)if(w[i])id.push_back(i);
printf("%.16lf",dfs(1,0,w[1])+c[1]);
}