BZOJ 4013 HNOI2015 实验比较 树形DP+组合数学
发布时间：2020-12-13 20:46:21 所属栏目：PHP教程 来源：网络整理
导读：题目大意：给定1张图，每条边有’=’和’’两个属性，每一个点入度最多为1，求这张图可以压成多少个用’=’和’’连接的序列 我只贴代码~~ 题解自己搜~~ #include cstdio #include cstring #include iostream #include algorithm #define M 110 #define MOD
|
题目大意：给定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,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,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;
}（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |