简要题意(我就感觉我在做阅读理解

给定$n+m$个字符串,以及字符串的阅读顺序(不全。

求最少的正反串都出现过的单词数。

考虑网络流,转化成求最小割

回文串特殊,无关于其他字串,贡献恒定为$1$,因此可以放在一边暂时不理。

若正、反串都出现,那么贡献为$2$,因此正串向反串建一条流量为$2$的边。

对于已经确定阅读顺序的行或列

对于正串(字典序较小的那个),不妨假设正串归于$S$集,反串归于$T$集。

那么如果是正向阅读,也就是$st$向正串连一条无限流量的边。

反之,也就是反串向$ed$连边。

对于未确定阅读顺序的行或列

它的阅读顺序决定于已确定阅读顺序的行或列。

也就是说如果已经出现了$xy$,那未确定中有$ab,xy$,不能出现$yx$,则必须需要正向阅读。

但是现在又出现了$ba$,那么不能出现$ab$,但是这样就自相矛盾了,则需要砍边。

因此需要反串向字符串连边,字符串向正串连边。

比如$st\rightarrow a_1\rightarrow b_1\rightarrow r_1\rightarrow a_2\rightarrow b_2-ed$

意思就是,已经确定的行和列中呢,有$a_1$这个正串,$b_2$这个反串,由于未确定行和列出现了$b_1,a_2$这样的模式串(未确定正反),但是不能同时满足$b_1,a_2 $相反阅读顺序的条件,则必须砍掉一些边使得网络不连通 。

更复杂的情况其实就是以上两种模型的叠加,就不讨论了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=1e4+5,M=1e4;const ull G=31;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int idx;
struct node{int x,y;};
namespace Hash
{
    ull pw[N];struct edge{int next,id1,id2;ull w;}a[50005];int len,last[50005];
    void clear(){memset(last,0,sizeof(last));len=0;}
    I bool ins(char *s,int n)
    {
        ull id=0;
        for(int i=1;i<=n;i++)id=id*G+(s[i]-'A');
        int k=id%99983;
        if(!last[k]){a[++len].w=id;a[len].id1=idx+1,a[len].id2=idx+2;last[k]=len;return 1;}
        for(k=last[k];k;k=a[k].next)
            if(a[k].w==id)return 0;
            else if(!a[k].next)break;
        a[++len].w=id;a[k].next=len;a[len].id1=idx+1,a[len].id2=idx+2;
        return 1;
    }
    node get(char *s,int n)
    {
        ull id=0;
        for(int i=1;i<=n;i++)id=id*G+(s[i]-'A');
        int k=id%49983;
        for(k=last[k];k;k=a[k].next)
            if(a[k].w==id)return (node){a[k].id1,a[k].id2};
        //a[++len].w=id;a[k].next=len;a[len].id1=idx+1,a[len].id2=idx+2;
    }
    
}
struct edge{int y,c,next;}a[N<<1];int len,last[N],cur[N];
void ins(int x,int y,int c)
{
    a[++len]=(edge){y,c,last[x]};last[x]=len;
    a[++len]=(edge){x,0,last[y]};last[y]=len;
}
int gap[N],d[N],q[N],l,r,st,ed,ans;
int ISAP(int x,int f)
{
    if(x==ed)return f;
    int s=0,t=0;
    for(int &k=cur[x],y;k;k=a[k].next)if(d[y=a[k].y]==d[x]-1)
    {
        s+=(t=ISAP(y,min(a[k].c,f)));
        f-=t;a[k].c-=t;a[k^1].c+=t;
        if(!f)return s;
    }
    if(!(--gap[d[x]]))d[s]=M;
    ++gap[++d[x]];cur[x]=last[x];
    return s;
}
void build()
{
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    q[1]=ed;l=1,r=1;++gap[d[ed]=1];
    for(int x=q[l];l<=r;x=q[++l])for(int k=last[x],y;k;k=a[k].next)if(!d[y=a[k].y])++gap[d[q[++r]=y]=d[x]+1];
    memcpy(cur,last,sizeof(cur));
    while(d[st]<M)ans+=ISAP(st,M);
}
I bool same(char *s1,char *s2,int l)
{
    for(int i=1;i<=l;i++)
        if(s1[i]!=s2[i])return 0;
    return 1;
}
I bool cmp(char *s1,char *s2,int l)
{
    for(int i=1;i<=l;i++)
        if(s1[i]<s2[i])return 1;
        else if(s2[i]<s1[i])return 0;
    return 1;
}
char s1[205],s2[205],s3[205],s[205];
void insert(char *s,int op,int x,int tmp)
{
    int flag; 
    for(int i=1,r;i<=tmp;i=r+1)
    {
        r=i;flag=1;
        while(r<=tmp&&s[r]!='_')++r;
        if(r==i)continue;
        int l=r-i;
        for(int j=1;j<=l;j++)s2[j]=s1[j]=s[j+i-1];
        reverse(s2+1,s2+l+1);
        if(same(s1,s2,l))
        {
            if(Hash::ins(s1,l))++ans;
            continue;
        }
        else if(!cmp(s1,s2,l))
        {
            flag*=-1;
            for(int j=1;j<=l;j++)s3[j]=s1[j];
            for(int j=1;j<=l;j++)s1[j]=s2[j];
            for(int j=1;j<=l;j++)s2[j]=s3[j];
        }
        flag*=op;
        if(Hash::ins(s1,l)){ins(idx+1,idx+2,2);idx+=2;}
        node q=Hash::get(s1,l);
        if(flag==1)ins(st,q.x,M);
        else if(flag==-1)ins(q.y,ed,M);
        else ins(q.y,x,M),ins(x,q.x,M);
    }
}
int row[105],col[105];
char ss[105][105];
int main()
{
//    file("data0");
    int T;qr(T);
    while(T--)
    {
        memset(last,0,sizeof(last));len=1;
        Hash::clear();ans=0;
        int n,m;qr(n),qr(m);
        for(int i=1;i<=n;i++)qr(row[i]);
        for(int i=1;i<=m;i++)qr(col[i]);
        for(int i=1;i<=n;i++)scanf("%s",ss[i]+1);
        st=0,ed=M-1;idx=n+m;
        for(int i=1;i<=n;i++)    
            insert(ss[i],row[i],i,m);
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
                s[j]=ss[j][i];
            insert(s,col[i],i+n,n);
        }
        build();
        qw(ans);puts("");
    }
    return 0;
}