題目大意：給定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;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
