题解 P4076 【[SDOI2016]墙上的句子】

· · 题解

题目大意

给出 n+m 个字符串 , 每个字符串包含若干单词 , 可以正着读也可以反着读 , 有些字符串已经确定了阅读方法 , 要求确定剩下字符串的阅读方法 , 使得正反串都出现的单词数最少.

保证对于同一个字符串内的单词 , 要么所有单词的正串字典序大于等于反串 , 要么所有单词的反串字典序大于等于正串.

solution

回文串一定产生 1 的贡献 , 单独处理

看到正反可以联想到 文理分科 , 类比这道题考虑最小割做法

一开始是想着直接将 n+m 个字符串作为被分的对象 , 然而并建不了图 , 因为对于单词来说这是存在性问题

转换思维 查阅题解 , 将单词作为被划分集合的对象

设源点为 s , 汇点为 t , 划分的两个集合为 S 与 T

将一个单词分为正串与反串两个节点 ( 这里正串定义为正反串中字典序较小的串 ) , 正串向反串连容量为 2 的边

正串被划分到 S 集合 \rightarrow 正串出现

正串被划分到 T 集合 \rightarrow 正串没有出现

反串被划分到 T 集合 \rightarrow 反串出现

反串被划分到 S 集合 \rightarrow 反串没有出现

当正串一定出现时 , s 向正串连容量为 INF 的边

当反串一定出现时 , 反串向 t 连容量为 INF 的边

接下来考虑那些没有确定读法的字符串

这里有一个重要条件

对于同一个字符串内的单词 , 要么所有单词的正串字典序大于等于反串 , 要么所有单词的反串字典序大于等于正串.

意味着一个字符串中所有出现的单词都是正串 , 或者是反串 ( 这里假设都是正串 )

设使得字符串中单词都是正串的读法是将字符串划入 S 集合

字符串被划入 S 集合 \rightarrow 正串出现

字符串被划入 T 集合 \rightarrow 反串出现

若字符串被划入 S 集合 , 其中出现的正串也一定在 S 集合 , 于是字符串向每个其中出现的单词的正串连 INF 边

若字符串被划入 T 集合 , 其中出现的反串也一定在 T 集合 , 于是字符串中出现单词的反串向字符串连 INF 边

code

#include <bits/stdc++.h>

using namespace std;

const int N = 7e2 + 5;
const int M = N * N;
const int INF = 0x3f3f3f3f;
int _w;

int head[N] , eidx , dep[N] , que[N] , he , ta , cur[N] , st , ed;
struct Edge { int nxt , to , flow , cap; } edge[M];

void addedge( int u , int v , int cap ) { 
  edge[++eidx] = (Edge) { head[u] , v , 0 , cap }; head[u] = eidx;
  edge[++eidx] = (Edge) { head[v] , u , 0 , 0 }; head[v] = eidx;
}

bool bfs( void ) {
  static int u;
  memset( dep , 0 , sizeof dep );
  dep[que[he = ta = 1] = st] = 1;
  while( he <= ta ) {
    u = que[he++];
    for( int i = head[u] , v ; ~i ; i = edge[i].nxt )
      if( !dep[v = edge[i].to] && edge[i].cap > edge[i].flow )
        dep[que[++ta] = v] = dep[u] + 1;
  }
  return dep[ed] != 0;
} 

int dfs( int u , int fl ) {
  if( u == ed || !fl ) return fl;
  int g = 0 , d;
  for( int & i = cur[u] ; ~i ; i = edge[i].nxt ) 
    if( dep[edge[i].to] == dep[u] + 1 && ( d = dfs( edge[i].to , min( edge[i].cap - edge[i].flow , fl - g ) ) ) ) {
      edge[i].flow += d , edge[i ^ 1].flow -= d;
      if( ( g += d ) >= fl ) break;
    }
  return g;
}

int dinic( void ) {
  int res = 0;
  while( bfs() ) {
    memcpy( cur , head , sizeof head );
    res += dfs( st , INF );
  }
  return res;
}

int n , m , col[N] , row[N] , idx;
char str[N][N];
set<string> pal;
map<string,int> id;

void analyze( string s , int type , int u ) {
  static int n; 
  static string a , b;
  n = s.length();
  for( int i = 0 , r , flag ; i < n ; i = r + 1 ) {
    r = i;
    if( s[i] == '_' ) continue;
    while( r < n - 1 && s[r + 1] != '_' ) ++r;
    a = s.substr( i , r - i + 1 );
    b = a; reverse( b.begin() , b.end() );
    if( b < a ) swap( a , b ) , flag = -1;
    else flag = 1;
    if( a == b ) {
      pal.insert( a );
      continue;
    }
    if( !id.count( a ) ) {
      id[a] = ++idx;
      id[b] = ++idx;
      addedge( idx - 1 , idx , 2 );
    } flag *= type;
    if( flag == 1 ) addedge( st , id[a] , INF );
    else if( flag == -1 ) addedge( id[b] , ed , INF );
    else addedge( id[b] , u , INF ) , addedge( u , id[a] , INF );
  }
}

void solve( void ) {
  _w = scanf("%d%d",&n,&m); idx = n + m;
  memset( head , -1 , sizeof head ) , eidx = -1;
  id.clear() , pal.clear();
  for( int i = 1 ; i <= n ; ++i ) _w = scanf("%d",row + i );
  for( int i = 1 ; i <= m ; ++i ) _w = scanf("%d",col + i );
  for( int i = 1 ; i <= n ; ++i ) _w = scanf("%s",str[i]+1);
  st = 0 , ed = N - 1;
  static string tmp;
  for( int i = 1 ; i <= n ; ++i ) {
    tmp = str[i] + 1;
    analyze( tmp , row[i] , i );
  }
  for( int i = 1 ; i <= m ; ++i ) {
    tmp = "";
    for( int j = 1 ; j <= n ; ++j )
      tmp += str[j][i];
    analyze( tmp , col[i] , i + n );
  }
  printf("%d\n",dinic() + int( pal.size() ) );
}

int main( void ) {
  int T;
  _w = scanf("%d",&T);
  while( T-- ) solve();
  return 0;
}