题目
题目描述
考古学家发现了一堵写有未知语言的白色墙壁，上面有一个n行m列的格子，其中有些格子内被填入了某个A至Z的大写字母，还有些格子是空白的。
一直横着或竖着的连续若干个字母会形成一个单词，且每一行的阅读顺序可能是从左向右或从右向左，每一列的阅读顺序可能是从下往上或从上往下。也就是说对于每一行来说，从左向右可以被看做是若干个单词形成的句子，相邻两个单词被一个或多个空白格子分割开来；也有可能是从右向左被看成是一个句子，竖直方向类似。
遗憾的是，我们并不完全知道每一行每一列的阅读顺序是怎样的。但可以猜测，有些单词会满足反转过来也是一个单词。例如单词BOY，翻转过来的YOB也是一个英文单词。
此外观察者发现，对每一行（列）来说，按照确定后的阅读顺序读出的所有单词同时满足“自己的字典序不小于翻转后的字典序”，或同时满足“自己的字典序不大于翻转后的字典序”。
在确定了所有行列的阅读顺序之后，我们可以构造出关于这种未知语言的字典。
请问字典中出现的“翻转过来也是一个单词”的单词最少有多少种请注意，如果一个单词翻转后是不同的另外一个单词，它们需要被分别计入；而对于本身是回文的单词则不需要重复计入
输入输出格式
输入格式：
第一行一个整数T，表示T组测试数据。
对于每一组数据来说：第一行输入两个整数n,m。
第二行给出了n个数字，对应n行，其中若第i个数字为1，则表示第i行的阅读顺序从左往右；若为-1则为从右向左；若为0则表示无法确定
第三行给出了m个数字，对应n行，其中若第i个数字为1，则表示第i列的阅读顺序从上往下；若为-1则为从下向上；若为0则表示无法确定
之后n行，每行给出了长度为m的字符串，由A~Z和下划线组成，对应了每个格子的符号，其中下划线表示格子为空。
输出格式：
输出T行。每一组数据输出一行一个整数，表示最少有多少个单词，满足翻转后依然是单词。
注意，如果一个单词是回文，那么它一定满足“翻转后依旧是单词”
输入输出样例
输入样例#1：
1
2 10
0 0
0 0 0 0 0 0 0 0 0 0
ADA_JARVIS
ADA_SIVRAJ
输出样例#1：
3
说明
对于100%的数据，1<=n,m<=72,T<=64
题解
我就是被卡死，不停
RE，写处理$10+k$，我也绝对不会用string写题！$2+k$就
AC了，string+map真是嗨到不行啊
数据范围就暗示了这是个网络流……
先把回文串摘出来
因为要求的是最小答案，考虑最小割
如果一个单词$A$翻转后仍是单词（假设是$B$），它会产生$2$的贡献，假设$A<B$，则$A$向$B$连一条流量为$2$的边
如果第$i$行是从左向右读的并且翻转后字典序大，则$S\to i\to 第i行的单词的A$，流量为$inf$，表示不可割；翻转后字典序小，则$第i行的单词B\to i\to T$，流量为$inf$
如果第$i$行没有确定阅读顺序，则$B\to i\to A$，流量为$inf$，表示无论从哪边读都可以
从右到左、从上到下、从下到上同理
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,N=101,inf=1e8;
struct p{
int x,y,d;
}c[MAX];
int T,n,m,num=1,tot,ans,t;
short FL;
short a[N],b[N];
int h[MAX],qu[MAX],H[MAX],d[MAX];
char s[N][N];
map<string,int> ma;
void add(int x,int y,int d=inf)
{
c[++num]=(p){h[x],y,d},h[x]=num;
c[++num]=(p){h[y],x,0},h[y]=num;
}
void Work(string A,int i,bool fl=0)
{
string B=A;
reverse(B.begin(),B.end());
if(A==B&&!ma[A]) ++ans,ma[A]=++tot;
if(A<B) FL=1;
else if(A>B) FL=-1,swap(A,B);
if(!ma[A]) ma[A]=++tot,ma[B]=++tot,add(ma[A],ma[B],2);
if(A==B) return;
if(fl) add(i,ma[A]),add(ma[B],i);
else if(FL==1) add(i,ma[A]);
else if(FL==-1) add(ma[B],i);
}
bool bfs()
{
memset(d,0,sizeof(d));
int hl=1,tl=d[0]=1;
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=h[tt];i;i=c[i].x)
if(!d[c[i].y]&&c[i].d)
{
d[c[i].y]=d[tt]+1,qu[++tl]=c[i].y;
if(c[i].y==T) return 1;
}
}
return 0;
}
int dfs(int x=0,int dix=inf)
{
if(x==T||!dix) return dix;
int sum=0;
for(int &i=H[x],dis;i;i=c[i].x)
if(d[c[i].y]==d[x]+1&&c[i].d)
{
dis=dfs(c[i].y,min(c[i].d,dix));
if(dis)
{
c[i].d-=dis,c[i^1].d+=dis,dix-=dis,sum+=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-2;
return sum;
}
int Dinic()
{
int tot=0,D;
while(bfs())
{
memcpy(H,h,sizeof(h));
while(D=dfs()) tot+=D;
}
return tot;
}
int main()
{
scanf("%d",&t);
while(t--)
{
num=1,ans=0,ma.clear();
memset(h,0,sizeof(h));
scanf("%d%d",&n,&m),tot=n+m,T=5*n*m+1;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=m;++i)
scanf("%d",&b[i]);
string A="",B="";
for(int i=1;i<=n;++i)
{
scanf("%s",s[i]+1),s[i][0]=s[i][m+1]='_',FL=0;
if(a[i]==1)
{
for(int j=1;j<=m+1;++j)
if(s[i][j]!='_') A+=s[i][j];
else if(A!="") Work(A,i),A="";
if(FL==1) add(0,i);
if(FL==-1) add(i,T);
}
else if(a[i]==-1)
{
for(int j=m;j>=0;--j)
if(s[i][j]!='_') A+=s[i][j];
else if(A!="") Work(A,i),A="";
if(FL==1) add(0,i);
if(FL==-1) add(i,T);
}
else for(int j=1;j<=m+1;++j)
if(s[i][j]!='_') A+=s[i][j];
else if(A!="") Work(A,i,1),A="";
}
for(int i=1;i<=m;++i)
{
s[0][i]=s[n+1][i]='_',FL=0;
if(b[i]==1)
{
for(int j=1;j<=n+1;++j)
if(s[j][i]!='_') A+=s[j][i];
else if(A!="") Work(A,i+n),A="";
if(FL==1) add(0,i+n);
if(FL==-1) add(i+n,T);
}
else if(b[i]==-1)
{
for(int j=n;j>=0;--j)
if(s[j][i]!='_') A+=s[j][i];
else if(A!="") Work(A,i+n),A="";
if(FL==1) add(0,i+n);
if(FL==-1) add(i+n,T);
}
else for(int j=1;j<=n+1;++j)
if(s[j][i]!='_') A+=s[j][i];
else if(A!="") Work(A,i+n,1),A="";
}
printf("%d\n",ans+Dinic());
}
return 0;
}
