Joining Byte Blocks（哈希+带花树）

题目链接

Problem Statement

As you are probably aware, the Internet protocols specify a canonical byte order convention for data transmitted over the network called network byte order, so that machines with different byte order conventions can communicate. But what if such canonical byte order didn't exist? We would probably be trapped in chaos trying to figure out the byte order for every machine we want to communicate with. But luckily, no matter the byte order (big-endian or little-endian), there will be byte blocks that will always be read correctly. 

Imagine you have a list of N byte blocks. In order to minimize the number of trasmission operations required to send all of them, you want to pair as many as possible blocks. Note that the resulting byte frame should have same representation in both network orders, i.e., they should be a palindrome when paired. The rules for such pairings are the following:

• No block can be paired with itself.
• A block can be paired zero or one time.
• You cannot pair more than two blocks.

For the ease of representation we will use lowercase latin characters to represent byte blocks. Suppose we have two blocks [′a′,′a′,′f′] and [′f′], and they are paired to form the frame [′f′,′a′,′a′,′f′], then it has the same representation in any of the byte order. 

Now, given the list of blocks, using the pairings described above, what's the minimum number of transmissions required to send them all?

Note: A block can either be transmitted alone, or paired with another block (if the pair satisfies above criteria).

Input Format

There will be multiple test cases per input file. Every test case will start with a number Ntelling you the size of the list. Then N lines follow, each one with a block, where each byte has been replaced by its current English alphabet lowercase letter. No test case will have more than 3000 potential pairs.

Output Format

Output a single line per test case in the input with the required answer.

Constraints

• 1≤number of test cases≤6
• 1≤N≤1000
• 1≤length of each block≤1000
• Each block consisits of lowercase latin characters, [′a′,′z′].

Sample Input

6
aaababa
aa
ababaaa
baaa
a
b
9
aabbaabb 
bbaabbaa
aa
bb
a
bbaa
bba
bab
ab

Sample Output

3
5

Explanation

• Sample Case #00: All of the blocks can be paired into following 3 frames.

  • "baaa" + "b" = "baaab"
  • "aaababa + "ababaaa" = "aaababaababaaa"
  • "aa" + "a" = "aaa"

• Sample Case #01: Following frames will be sent

  • "aabbaabb" + "bbaabbaa" = "aabbaabbbbaabbaa"
  • "aa" + "a = "aaa"
  • "bba" + "bb" = "bbabb"
  • "bab" + "ab" = "babab"
  • "bbaa"

又一个之前没有用过的字符串hash的应用。还加了个一般图最大匹配的模板。

AC代码：

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define mem(a, b) (memset(a, b, sizeof(a)))
#define pb push_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, m) for (int i = 0; i < (int)(m); i++)
#define rep2(i, n, m) for (int i = n; i < (int)(m); i++)
typedef long long LL;
typedef pair<LL, LL> PLL;

const int oo = (int) 1e9;
const double PI = 2 * acos(0);
const double eps = 1e-9;
const int MAX_N = 2048;

const int P = 131;
const int Q = 191;
const int MP = 1000003;
const int MQ = 10000019;
LL pw[MAX_N], qw[MAX_N];
char str[MAX_N];
#define F first
#define S second

/* 采用两个hash函数*/
struct strHash {
    PLL str, rev;
    int len;

    strHash operator +(const strHash &o) const {
        strHash res;
        res.str.F = (str.F * pw[o.len] + o.str.F) % MP;
        res.str.S = (str.S * qw[o.len] + o.str.S) % MQ;
        res.rev.F = (o.rev.F * pw[len] + rev.F) % MP;
        res.rev.S = (o.rev.S * qw[len] + rev.S) % MQ;
        res.len = len + o.len;
        return res;
    }
}s[MAX_N];

void init() {
    pw[0] = qw[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        pw[i] = pw[i-1] * P % MP;
        qw[i] = qw[i-1] * Q % MQ;
    }
}

strHash makeHash(const char *str) {
    strHash res;
    res.len = strlen(str);
    res.str.F = res.str.S = 0;
    for (int i = 0; i < res.len; i++) {
        res.str.F = (res.str.F * P + str[i]) % MP;
        res.str.S = (res.str.S * Q + str[i]) % MQ;
    }
    res.rev.F = res.rev.S = 0;
    for (int i = res.len-1; ~i; i--) {
        res.rev.F = (res.rev.F * P + str[i]) % MP;
        res.rev.S = (res.rev.S * Q + str[i]) % MQ;
    }
    return res;
}

/* 判断a+b 或者 b+a是否为回文 */
inline bool check(const strHash &a, const strHash &b) {
    strHash u = a + b;
    if (u.str == u.rev) return true;
    strHash v = b + a;
    if (v.str == v.rev) return true;
    return false;
}


/* 一般图最大匹配(带花树) */
const int MAX = 2048;
struct GraphMatch {
  int Next[MAX];
  int spouse[MAX];
  int belong[MAX];

  int findb(int a) {
    return belong[a]==a?a:belong[a]=findb(belong[a]);
  }
  void together(int a,int b){
    a=findb(a),b=findb(b);
    if (a!=b)belong[a]=b;
  }

  vector<int> E[MAX];
  int N;
  int Q[MAX],bot;
  int mark[MAX];
  int visited[MAX];

  int findLCA(int x,int y){
    static int t=0;
    t++;
    while (1) {
      if (x!=-1) {
              x = findb(x);
              if (visited[x]==t)return x;
              visited[x]=t;
              if (spouse[x]!=-1)x=Next[spouse[x]];
              else x=-1;
          }
          swap(x,y);
      }
  }

  void goup(int a,int p){
    while (a!=p){
          int b=spouse[a],c=Next[b];
          if (findb(c)!=p)Next[c]=b;
          if (mark[b]==2)mark[Q[bot++]=b]=1;
          if (mark[c]==2)mark[Q[bot++]=c]=1;
          together(a,b);
          together(b,c);
          a=c;
      }
  }

    void findaugment(int s){
      for (int i=0;i<N;i++) {
          Next[i]=-1;
          belong[i]=i;
          mark[i]=0;
          visited[i]=-1;
      }
      Q[0]=s;bot=1;mark[s]=1;
      for (int head=0;spouse[s]==-1 && head<bot;head++){
          int x=Q[head];
          for (int i=0;i<(int)E[x].size();i++){
                int y=E[x][i];
                if (spouse[x]!=y && findb(x)!=findb(y) && mark[y]!=2){
                    if (mark[y]==1){
                        int p=findLCA(x,y);
                        if (findb(x)!=p)Next[x]=y;
                        if (findb(y)!=p)Next[y]=x;
                        goup(x,p);
                        goup(y,p);
                    }else if (spouse[y]==-1){
                        Next[y]=x;
                        for (int j=y;j!=-1;){
                            int k=Next[j];
                            int l=spouse[k];
                            spouse[j]=k;spouse[k]=j;
                            j=l;
                        }
                        break;
                    }else{
                        Next[y]=x;
                        mark[Q[bot++]=spouse[y]]=1;
                        mark[y]=2;
                    }
                }
            }
        }
    }

    void init(int n) {
      N = n;
      for (int i = 0; i < N; ++i) {
        E[i].clear();
      }
    }

    void addEdge(int a, int b) {
      E[a].push_back(b);
      E[b].push_back(a);
    }

    int maxMatch() {
      int ret = 0;
      for (int i = 0; i < N; ++i) spouse[i] = -1;
      for (int i = 0; i < N; ++i) {
        if (spouse[i] == -1) {
          findaugment(i);
        }
      }
      for (int i = 0; i < N; ++i) {
        if (spouse[i] != -1) ++ret;
      }
      return ret;
    }
} match;


int main(void) {
    init();
    int N;
    while (~scanf("%d", &N)) {
        for (int i = 0; i < N; i++) {
            scanf("%s", str);
            s[i] = makeHash(str);
        }

        match.init(N);
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (check(s[i], s[j])) {
                    match.addEdge(i, j);
                }
            }
        }
        int cnt = match.maxMatch();
        /*
         for (int i = 0; i < N; i++) {
             printf("%d %d
", i, match.spouse[i]);
         }
         */
        printf("%d
", N - cnt / 2);
    }

    return 0;
}