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个点独立。

第一件事是这样的：每个点都是匹配边的一个端点。右边被选的点一定是被匹配过的。左边被选的点的右边一定是不选的。

第二件事是这样的：如果有一条边没被覆盖，讨论一下发现不管这条边是不是匹配边，都不可能左边没标记右边有标记。

#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;
}