首页 > 代码库 > HDU 4921 Map DFS+状态压缩+乘法计数

HDU 4921 Map DFS+状态压缩+乘法计数

2024-07-18 00:28:58   211人阅读

算最多十条链，能截取某前缀段，每种方案都可以算出一个权值，每种方案的概率都是总数分之一，问最后能构成的所有可能方案数。

对计数原理不太敏感，知道是DFS先把链求出来，但是想怎么统计方案的时候想了好久，其实因为只能取某个链的前缀，所以直接取链长加+1 然后相乘即可，当然因为会出现都是空的那种情况，要去掉，全部乘完之后，要-1

然后就是算权值了，权值等于当前加进来的点的总和 以及 等级相同的点的加成，并不是特别好算，这时候考虑每个状态下的点对全局的贡献，对，就是这个思想，用状态压缩来表示状态，然后这个状态占用的所有情况，又可以用乘法原理乘出来。然后对这个状态算出权值之后，乘以所有的占用情况即可

下标是从0开始的，注意

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int N = 10010;int u[N],v[N],ft[N],nt[N];int ind[N],deep[N],val[N],vis[N];int n,m,cnt;vector <int> ve[20];int dir[20],sz[1100],cur;void init(){    for (int i=0;i<=n;i++){        ft[i]=-1;        ind[i]=0;        vis[i]=0;    }    cnt=0;    cur=0;    for (int i=0;i<20;i++){        ve[i].clear();    }    for (int i=0;i<1100;i++) sz[i]=0;}void add(int a,int b){    u[cnt]=a;    v[cnt]=b;    nt[cnt]=ft[a];    ft[a]=cnt++;}void dfs(int x){    if (vis[x]) return;    vis[x]=1;    for (int i=ft[x];i!=-1;i=nt[i]){        int vx=v[i];        if (vis[vx]) continue;        ve[cur-1].push_back(vx);        int len=ve[cur-1].size();        sz[len-1]++;        dfs(vx);    }}int main(){    int t,a,b;    scanf("%d",&t);    while (t--)    {        scanf("%d%d",&n,&m);        init();        for (int i=0;i<n;i++){            scanf("%d",&val[i]);        }        while (m--)        {            scanf("%d%d",&a,&b);            add(a,b);            ind[b]++;        }        for (int i=0;i<n;i++){            if (vis[i]==0 && ind[i]==0){                dir[cur++]=i;                ve[cur-1].push_back(i);                dfs(i);                sz[0]++;            }        }        double tot=1;        int maxn=0;        for (int i=0;i<cur;i++){            int tmp=ve[i].size();            maxn=tmp>maxn?tmp:maxn;            tot*=(double)(tmp+1);        }        tot-=1;        double ans=0,sum=0;        for (int i=0;i<maxn;i++){           // cout<<"Test "<<i<<endl;            for (int j=1;j<(1<<cur);j++){                //cout<<"sta "<<j<<endl;                sum=0;                int tmp=0;                double calc=1.0;                for (int k=0;k<cur;k++){                    int r=ve[k].size();                    bool flag=((1<<k)&j);                    if (r<=i && flag){                        sum=0;                        break;                    }                    if (i<r && flag){                        sum+=(double)val[ve[k][i]];                        tmp++;                        calc*=(double)(r-i);                    }                    else                    {                        calc*=(min(r,i)+1)*1.0;                    }                }                //cout<<"calc "<<calc<<endl;                //cout<<"sum "<<sum<<endl;                ans+=sum*calc;                if (tmp>1) ans+=calc*(double)tmp/(double)sz[i]*sum;               // cout<<"ans "<<ans<<endl;            }        }        //cout<<"cur "<<cur<<endl;        //cout<<ans<<" "<<tot<<endl;        ans=ans/tot;        printf("%.3lf\n",ans);    }    return 0;}

　　


联系
我们