Gym102341B Bulbasaur

Link
先利用最大流最小割定理将要求的转化为最小割，然后就可以转化为删掉最少的点使得两层不连通。
我们先考虑([1,i])层，设(f_{s,j})表示使得第(i)层有且仅有(S)中的点能够到达(j)层，最少需要删掉的点数。
显然(f_{s,j})关于(j)单调，并且(f_{s,j}in[0,m])。
那么我们升序枚举(i)，然后对于同一个(s)，维护值不相同的(f_{s,j})的(j)之间的分界线。转移是非常简单的。

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,m,to[10];long long ans;
struct node
{
    int pos[10];
    node(){memset(pos,0,40);}
    int&operator[](int x){return pos[x];}
}f[1<<9],t[1<<9];
void merge(node&p,node q)
{
    if(p[0]>q[0]) std::swap(p,q);
    for(int i=m;~i;--i) if(q[i]==q[0]) q[i]=p[0];
    for(int i=1;i<=m;++i) p[i]=std::max(p[i],q[i]);
}
node up(node x){for(int i=m;i;--i)x[i]=x[i-1];return x;}
int get(){char c=getchar();while(!isdigit(c))c=getchar();return c&15;}
int cal(int s){int r=0;for(int i=0;i<m;++i)if(s>>i&1)r|=to[i];return r;}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<1<<m;++i) for(int j=0;j<=m;++j) f[i][j]=j<=m-__builtin_popcount(i)? 1:n+1;
    for(int i=2;i<=n;++i)
    {
	memset(to,0,m<<2);
	for(int j=0;j<1<<m;++j) for(int k=0;k<=m;++k) t[j][k]=n+1;
	for(int j=0;j<m;++j) for(int k=0;k<m;++k) if(get()) to[j]|=1<<k;
	for(int j=0;j<1<<m;++j) merge(t[cal(j)],f[j]);
	std::swap(f,t);
	for(int j=(1<<m)-1;j;--j){node r=up(f[j]);for(int k=0;k<m;++k) if(j>>k&1) merge(f[j^1<<k],r);}
	for(int j=0;j<1<<m;++j) for(int k=0;k<=m-__builtin_popcount(j);++k) f[j][k]=std::min(f[j][k],i);
	for(int j=1;j<=m;++j) ans+=i-f[0][j];
    }
    printf("%lld",ans);
}