淮安经济技术开发区建设局网站,成都网站seo外包,做网站客户要先看效果后付款,无锡百度seo优化题目链接 神难qwq。配合rqy的博客食用。 首先我们学到有一个概率函数$p(x)$表示某事件发生概率取值小于x的函数。这个函数有什么特点呢#xff1f; 那就是$\int_{-∞}^{∞}p(x)dx1$ 这个是显然的 然后我们令p(x)为首次联通的时间的概率分布函数 这其实等价于生成树的最大权边等… 题目链接 神难qwq。配合rqy的博客食用。 首先我们学到有一个概率函数$p(x)$表示某事件发生概率取值小于x的函数。这个函数有什么特点呢 那就是$\int_{-∞}^{∞}p(x)dx1$ 这个是显然的 然后我们令p(x)为首次联通的时间的概率分布函数 这其实等价于生成树的最大权边等于x的概率对不对我虚啊我很可能理解错的 然后呢就有一个期望的式子 $EX\int tp(t)dt$ 我忘了是为什么了上午rqy才刚给我讲过现在就忘了我太菜了。 然后本题中期望就是$EX\int_{0}^{1}xp(x)dx$ $\int_{0}^{1}p(x)( \int_{0}^{x}1ds)dx$ $\int_{0}^{1}(\int_{s}^{1}p(x)dx)ds$ 然后我们把括号里面那个玩意设成P(s)好了 所以原式被我们化成了$\int_{0}^{1}P(s)ds$ 然后……emm等一会我忘了我要干嘛了qwq …… 然后我们设一个$f_{x,S}$表示集合SS包含1节点在x时刻前不连通x时刻恰好联通的概率 因为在x时刻不连通所以我们考虑它的转移 $f_{x,S}\sum\limits_{1属于S}^{S包含于S}(1-f_{x,S})(1-x)^{T(S,S-S)}$ 这什么意思呢 我们设T(A,B)为A点集和B点集之间的边数。 首先我们看见里面有一个$(1-f_{x,S})$这个玩意的意思是 既然我们的S集合要恰好联通那在这之前S作为S的一个子集是一定要联通的。而f表示的是不连通的概率所以就是1-x呗。 而且S和外界不要联通。 既然S和外界不要联通那每条边在x时刻不连通的概率是(1-x)那T条边都不连通的概率就是$(1-x)^{T(S,S-S)}$ 所以说$f_{x,S}$就是这么一个玩意儿。 然后我们把x当成参就有了$f_{S}(x)$这么一个东西。 然后……比如说有个全集U 最后我们求的就是这么一个玩意 $\int_{0}^{1}f_{U}(x)dx$ 然后下面的我就全忘了顺着rqy的笔迹讲不过我自己也看不懂是在干嘛qwq 我们设$dp_{S,k}\int_{0}^{1}f_{S}(x)(1-x)^{k}dx$ $\int_{0}^{1}(\sum\limits_{1属于S}^{S包含于S}(1-f_{S}(x))(1-x)^{T(S,S-S)})(1-x)^{k}dx$ 设tT(S,S-S) $dp_{S,k}\sum\limits_{1属于S}^{S包含于S}\int_{0}^{1}(1-f_{S}(x))(1-x)^{tk}dx$ $\sum\limits_{1属于S}^{S包含于S}\int_{0}^{1}(1-x)^{tk}-f_{S}(x)(1-x)^{tk}dx$ 我们发现后面那个玩意等于$dp_{S,tk}$ 就可以搞啦。至于k到底干嘛的rqy说不表示实际意义只是用来简化计算我没听懂。qwq 最后求的答案就是$dp_{U,0}$ 然后就是递归搞一搞DP输出。 当然到考场上如果碰到这道题我倾向于手玩。智商-INFqwq。 #includecstdio
#includecstring
#includecctype
#includealgorithm
#includecstdlib
#define maxn 11
#define maxm 55
inline long long read(){long long num0,f1;char chgetchar();while(!isdigit(ch)){if(ch-) f-1;chgetchar();}while(isdigit(ch)){numnum*10ch-0;chgetchar();}return num*f;
}double f[1maxn][maxm];
int q[1maxn][1maxn];
bool vis[1maxn][maxm];double dfs(int state,int t){if(state1) return 0;if(vis[state][t]) return f[state][t];vis[state][t]1;double ans(f[state][t].0);for(int sta(state-1)state;sta!state;sta(sta-1)state)if(sta1){ans1.0/(tq[sta][state(~sta)]1);ans-dfs(sta,tq[sta][state(~sta)]);}return ans;
}int main(){int nread(),mread();int Max1n;for(int i1;im;i){int aread(),bread();a--;b--;for(int sta0;staMax;sta){if(((staa)1)0) continue;for(int stb0;stbMax;stb){if(((stbb)1)0) continue;q[sta][stb]; q[stb][sta];}}}printf(%.6lf,dfs(Max-1,0));return 0;
} 转载于:https://www.cnblogs.com/cellular-automaton/p/8268088.html
