您当前位置：首页 > php开源 > php教程 > BZOJ 4013 HNOI2015 实验比较树形DP+组合数学

BZOJ 4013 HNOI2015 实验比较树形DP+组合数学

来源：程序员人生发布时间：2015-08-06 10:28:04 阅读次数：3145次

题目大意：给定1张图，每条边有’=’和’<’两个属性，每一个点入度最多为1，求这张图可以压成多少个用’=’和’<’连接的序列
我只贴代码~~
题解自己搜~~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 110
#define MOD 1000000007
using namespace std;
struct abcd{
    int to,next;
}table[M];
int head[M],tot;
int n,m;
int C[M][M],f[M][M];
int a[M][M],degree[M];
int v[M],T;
void Add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}
namespace Union_Find_Set{
    int fa[M];
    int Find(int x)
    {
        if(!fa[x]||fa[x]==x)
            return fa[x]=x;
        return fa[x]=Find(fa[x]);
    }
    void Union(int x,int y)
    {
        x=Find(x);y=Find(y);
        if(x==y) return ;
        fa[x]=y;
    }
}
void Pretreatment()
{
    int i,j;
    for(i=0;i<=n;i++)
    {
        C[i][0]=1;
        for(j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
}
void DFS(int x)
{
    int i;
    v[x]=T;
    for(i=head[x];i;i=table[i].next)
    {
        if(v[table[i].to]==T)
            throw true;
        if(v[table[i].to])
            continue;
        DFS(table[i].to);   
    }
}
void Tree_DP(int x)
{
    int i,j,k,l;
    f[x][0]=1;
    for(i=head[x];i;i=table[i].next)
    {
        Tree_DP(table[i].to);
        static int g[M];
        memset(g,0,sizeof g);
        for(j=1;j<=n;j++)
            for(k=0;k<=j;k++)
                for(l=j-k;l<=j;l++)
                    ( g[j] += (long long) f[x][k] * f[table[i].to][l] % MOD * C[j][k] % MOD * C[k][k+l-j] % MOD )%=MOD;
        memcpy(f[x],g,sizeof g);
    }
    for(i=n+1;i;i--)
        f[x][i]=f[x][i-1];
    f[x][0]=0;
}
int main()
{
    using namespace Union_Find_Set;
    int i,j,x,y;
    char p[10];
    cin>>n>>m;
    Pretreatment();
    for(i=1;i<=m;i++)
    {
        scanf("%d%s%d",&x,p,&y);
        if(p[0]=='=')
            Union(x,y);
        else
            Add(x,y);
    }
    for(x=1;x<=n;x++)
        for(i=head[x];i;i=table[i].next)
            a[Find(x)][Find(table[i].to)]=1;
    memset(head,0,sizeof head);
    tot=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j])
                Add(i,j),degree[j]++;
    for(i=1;i<=n;i++)
        if(Find(i)==i&&!v[i])
        {
            try
            {
                ++T;
                DFS(i);
            }
            catch(bool)
            {
                cout<<0<<endl;
                return 0;
            }
        }
    for(i=1;i<=n;i++)
        if(Find(i)==i&&!degree[i])
            Add(0,i);
    Tree_DP(0);
    int ans=0;
    for(i=1;i<=n+1;i++)
        (ans+=f[0][i])%=MOD;
    cout<<ans<<endl;
    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 svg点击事件不灵敏之解决方案

下一篇 >>fun:httpPost/httpGET>>功能:向$url POST/GET 数据

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点

BZOJ 4013 HNOI2015 实验比较 树形DP+组合数学

BZOJ 4013 HNOI2015 实验比较树形DP+组合数学