[HNOI2015]实验比较树形dp+组合数学

在合并的时候有可以加等于，或者继续用小于，
比如siz[x]和siz[y]合并，小于的区间为max(siz[x],siz[y])<=k<=siz[x]+siz[y]，
然后就是合并成多少个小于号的方案数了，
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<cstdlib>
  7 #define N 107
  8 #define M 207
  9 #define mod 1000000007
 10 #define ll long long
 11 using namespace std;
 12 
 13 int n,m,S;
 14 int cnt,head[N],next[M],rea[M];
 15 int fa[N],du[N],siz[N];
 16 bool boo[N],hash[N];
 17 struct Node
 18 {
 19     int x,y;
 20 }a[N];
 21 ll c[N][N],f[N][N],g[N],ans;
 22 
 23 void add(int u,int v)
 24 {
 25     next[++cnt]=head[u];
 26     head[u]=cnt;
 27     rea[cnt]=v,du[v]++;
 28 }
 29 int find(int num)
 30 {
 31     if (fa[num]!=num) fa[num]=find(fa[num]);
 32     return fa[num];
 33 }
 34 void dfs(int u,int fa)
 35 {
 36     boo[u]=1;bool flag=0;
 37     for (int i=head[u];i!=-1;i=next[i])
 38     {
 39         int v=rea[i];
 40         if (v==fa) continue;
 41         dfs(v,u);
 42         if (flag)
 43         {
 44             memset(g,0,sizeof(g));
 45             for (int i1=1;i1<=siz[u];i1++)
 46                 if (f[u][i1])
 47                 for (int j1=1;j1<=siz[v];j1++)
 48                     if (f[v][j1])
 49                     for (int k1=max(i1,j1);k1<=i1+j1;k1++)
 50                         g[k1]=(g[k1]+f[u][i1]*f[v][j1]%mod*c[k1][i1]%mod*c[i1][j1-(k1-i1)]%mod)%mod;
 51             siz[u]+=siz[v];
 52             for (int i=1;i<=siz[u];i++)
 53                 f[u][i]=g[i];            
 54         }
 55         else
 56         {
 57             flag=1;
 58             siz[u]=siz[v];
 59             for (int i=1;i<=siz[v];i++)
 60                 f[u][i]=f[v][i];
 61         }
 62     }
 63     if (u!=S)
 64     {
 65         siz[u]++;if (!flag) f[u][1]=1;
 66         else for (int i=siz[u];i>=1;i--) f[u][i]=f[u][i-1];
 67     }
 68 }
 69 bool dfs_circle(int u)
 70 {
 71     for (int i=head[u];i!=-1;i=next[i])
 72     {
 73         int v=rea[i];
 74         if (boo[v]) return false;
 75         boo[v]=true;
 76         if (!dfs_circle(v)) return false;
 77     }
 78     return true;
 79 }
 80 int main()
 81 {
 82     memset(head,-1,sizeof(head));
 83     scanf("%d%d",&n,&m);
 84     for (int i=1;i<=n;i++)
 85         fa[i]=i;
 86     for (int i=0;i<=n;i++)
 87         c[i][0]=1;
 88     for (int i=1;i<=n;i++)
 89         for (int j=1;j<=i;j++)
 90             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
 91 //========================================================================================    
 92     int x,y,top=0;char ch[2];
 93     for (int i=1;i<=m;i++)
 94     {
 95         scanf("%d%s%d",&x,&ch,&y);
 96         if (ch[0]=='=')
 97         {
 98             int u=find(x),v=find(y);
 99             fa[v]=u;
100             continue;
101         }
102         else if (ch[0]=='>') swap(x,y);
103         a[++top].x=x,a[top].y=y;
104     }
105     m=top;
106     for (int i=1;i<=m;i++)
107     {
108         int u=find(a[i].x),v=find(a[i].y);
109         if (u!=v) add(u,v);//如果一个相等集合中有相互比较关系 
110         else
111         {
112             printf("0
");
113             return 0;
114         }
115     }
116     for (int i=1;i<=n;i++)
117         if (!boo[i])
118         {
119             boo[i]=1;
120             if (!dfs_circle(i))
121             {
122                 printf("0
");
123                 return 0;
124             }
125         }
126     S=n+1;
127     for (int i=1;i<=n;i++)
128     {
129         int zhi=find(i);
130         if (!du[zhi]&&!hash[zhi])
131         {
132             add(S,zhi);
133             hash[zhi]=1;
134         }
135     }
136 //=========================================================================================
137     dfs(S,-1);
138     for (int i=1;i<=siz[S];i++)
139         ans=(ans+f[S][i])%mod;
140     printf("%lld
",ans);
141 }
[HNOI2015]实验比较 树形dp+组合数学

[HNOI2015]实验比较树形dp+组合数学
