CF590E Birthday Dilworth定理构造

发表于 更新于 分类于 阅读次数：

CF590E Birthday 首先字符串的包含关系可以直接AC自动机。需要找出每个串能匹配到的所有子串。根据下文中提到的东西，只需要找出每个位置为结尾，能匹配到的最长串，即$fail_x$能匹配到的串即可（传递性）。 之后，得到偏序关系。要求的就是它的最长反链，也就是最小链覆盖。注意Dilworth定理中的覆盖是可重的。 这里的偏序关系是DAG，传递闭包后可以当作不可重的。那么跑一个二分图匹配。 然后构造方案，就是这个题[CTSC2008]祭祀。开始补习二分图基础知识： 首先DAG二分图匹配的原理： 首先构造最大独立集$I$。后面说怎么构造，假装已经有了。 那么选取两个点都在独立集内的点为答案就行了。它们构成最大反链$A$集合。 证明大概是这样的：首先这肯定是反链，因为是独立集里选的。令有$n$个点，匹配为$m$，则独立集大小为$2n-m$。其中$\notin A$的点，一定是只有一端$\in I$的，不超过$n$个。也就是说选取的集合$ \geq n-m$。而反链大小就是这个数，说明构造出的就是反链。 关于怎么选独立集：选最小点覆盖的补集即可 关于怎么选最小点覆盖： 从任意没有被选取的右边的点开始DFS。去左边只能走没选的边，去右边只能走选了的边。选取左边被访问，右边没有被访问的点集就是最小点覆盖。 （左右换一下当然没关系，网上都是这么写的而已） 证明大概是这样的（这里）： 这个叫König定理。两件事：有$m$个点，这$m$个点独立。 第一件事是这样的：每个点都是匹配边的一个端点。右边被选的点一定是被匹配过的。左边被选的点的右边一定是不选的。 第二件事是这样的：如果有一条边没被覆盖，讨论一下发现不管这条边是不是匹配边，都不可能左边没标记右边有标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using std::cerr;
using std::endl;

const int N = 1e7 + 233, M = 755;

int n, st[N], len[N], size; char str[N], buc[N];

int ch[N][2], fail[N], tot, end[N];
std::queue<int> que;

inline void insert(int id) {
  int now = 0;
  for (int i = 1; i <= len[id]; ++i) {
    int c = str[i] - 'a';
    if (!ch[now][c])
      ch[now][c] = ++tot;
    now = ch[now][c];
  }
  end[now] = id;
  // cerr << now << " " << id << endl;
}

inline void build() {
  if (ch[0][0]) que.push(ch[0][0]);
  if (ch[0][1]) que.push(ch[0][1]);
  while (!que.empty()) {
    int x = que.front(); que.pop();
    for (int i = 0; i < 2; ++i) {
      if (!ch[x][i])
        ch[x][i] = ch[fail[x]][i];
      else {
        fail[ch[x][i]] = ch[fail[x]][i];
        que.push(ch[x][i]);
        if (!end[ch[x][i]])
          end[ch[x][i]] = end[fail[ch[x][i]]];
      }
    }
  }
}

int G[M][M];

inline void match(char str[], int id) {
  int now = 0;
  for (int i = 1; i <= len[id]; ++i) {
    int c = str[i] - 'a';
    now = ch[now][c];
    if (end[now])
      G[id][end[now]] = 1;
    if (end[fail[now]])
      G[id][end[fail[now]]] = 1;
  }
}

int vis[M * 2], mat[M * 2], cnt;

int hungry(int x, int tag) {
  for (int y = 1; y <= n; ++y) {
    if (!G[x][y]) continue;
    if (vis[y + n] != tag) {
      vis[y + n] = tag;
      if (!mat[y + n]  hungry(mat[y + n], tag)) {
        mat[x] = y + n, mat[y + n] = x;
        return 1;
      }
    }
  }
  return 0;
}

int pick[M * 2];

void dfs(int x) {
  if (vis[x]) return;
  vis[x] = 1;
  for (int y = 1; y <= n; ++y)
    if (G[x][y] && !vis[y + n])
      vis[y + n] = 1, dfs(mat[y + n]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", str + 1);
    len[i] = strlen(str + 1);
    st[i] = size + 1;
    for (int j = 1; j <= len[i]; ++j)
      buc[++size] = str[j];
    insert(i);
  }
  build();
  for (int i = 1; i <= n; ++i)
    match(buc + st[i] - 1, i);
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        G[i][j] = G[i][k] & G[k][j];

  for (int i = 1; i <= n; ++i)
    G[i][i] = 0;
  for (int i = 1; i <= n; ++i)
    cnt += hungry(i, i);
  printf("%d\n", n - cnt);
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i)
    if (!mat[i])
      dfs(i);
  for (int i = 1; i <= n; ++i)
    if (vis[i] && !vis[i + n])
      printf("%d ", i);
  putchar('\n');
  return 0;
}