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

题目大意:给定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;
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 4013 HNOI2015 实验比较 树形DP+组合数学

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡