[UVA 11600] Masud Rana-白红宇

[UVA 11600] Masud Rana

阅读量：6793 次

发布时间：2019-06-26

本文共 1398 字，大约阅读时间需要 4 分钟。

图片加载可能有点慢，请跳过题面先看题解，谢谢

还是先缩点吧，把那些已经可以互相到达的点缩起来。（直接暴力 \(dfs\) 缩就行）

我们设 \(f(x,S)\) 为，当前在 \(x\) 点，已经已经处理完的点的状态为 \(S\) （一个二进制数）的期望值（这里的点是缩点之后的点）

那么假设这时我们已经处理完的点数为 \(ret\) ，则我们走到没处理完的点上的概率为 \(\frac{n-ret}{n-1}\)，所以我们需要走平均 \(\frac{n-1}{n-ret}\) 次才能走到那些未处理的点上

所以有转移：\(f(x,S)=\sum_{!(S\wedge (1<<i))}{\frac{f(i,S\vee (1<<i) )*size[i]}{n-ret}}\)

//made by Hero_OF_Someone#include
    
     #include
     
      #include
      
       #include
       
        #include
        #define db double#define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int T,t,n,m;bool vis[54];int size[54],cnt;map
         
           f[54];int num,head[54],nxt[1008],to[1008];il void add(int u,int v){ nxt[++num]=head[u];to[num]=v;head[u]=num; nxt[++num]=head[v];to[num]=u;head[v]=num;}il void init(){ num=0; memset(head,0,sizeof(head)); cnt=0; memset(vis,0,sizeof(vis)); n=gi(),m=gi(); for(int i=1;i<=m;i++){ int u=gi(),v=gi(); add(u,v); }}il int dfs(int x){ vis[x]=1; int ret=1; for(int i=head[x];i;i=nxt[i]){ int v=to[i]; if(vis[v]) continue; ret+=dfs(v); } return ret;}il db DP(int x,int S){ if(f[x].count(S)) return f[x][S]; int ret=0; for(int i=0;i

转载于:https://www.cnblogs.com/Hero-of-someone/p/7676955.html

你可能感兴趣的文章