题目大意：给定一张图，每条边有’=’和’<’两个属性，每个点入度最多为1，，求这张图可以压成多少个用’=’和’<’连接的序列 我只贴代码~~ 题解自己搜~~
;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);elseAdd(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;}
获得幸福的二法门是珍惜你所拥有的、遗忘你所没有的
