#20. Dilworth 定理输出方案
板子：CTSC2008 祭祀
描述：给定一个 DAG，求其最大反链，并输出方案。
一个 DAG 中最长反链的大小，等于其中最小可重链覆盖大小。
（我记得有一个假题叫大山王国的城市规划，所有题解都忘了可重两个字。
原因是 Dilworth 定理里描述的是偏序集，而我们的 DAG 求完传递闭包之后才是偏序集。
具体证明我记得有一篇很抽象的洛谷日报讲的这个，在不久的之前我也是会的，但是要 noi 了，直接略过。
我不想详细描述了啊，求答案就是
算了描述一下好构造：
对于一个点，最多一个前驱，一个后继。限制出度入读，考虑拆点成出点和入点，出向入连边。
先构造一个二分图的最大独立集。
具体的，求出最大匹配后，从右侧的非匹配点开始 dfs，从右往左只能走非匹配边，从左往右只能走匹配边。
这样，所有左侧 dfs 到的和右侧没有 dfs 到的点，构成一个最小点覆盖！
证明：
二分图最小点覆盖=最大匹配。右侧所有非匹配点都不在集合里，所有左侧匹配点不在集合中的右侧匹配点都在集合里。而所有右侧匹配点不在集合中，一定是左侧匹配点被遍历了也在集合中。所以所有匹配边都有恰好一个点在集合里。
覆盖全部边是显然的。
取这个集合的补集即为最大独立集。
对于出点和入点均在最大独立集中的点，即为最长反链中的点。
最小字典序最大反链
等价于这题的第三问。借用兔子的描述：对于一个点，这只要默认该点被选中，也就是删除这个点和与其有偏序关系的所有点后，再求一次最长反链，如果最长反链的大小只减小了
#include <bits/stdc++.h>
using namespace std;
const int maxn = 405, maxm = 4e3 + 5;
template <typename T>
void read(T &x)
{
T sgn = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= sgn;
}
struct node
{
int pre, to, val;
}edge[maxm << 1];
int head[maxn], cur[maxn], tot = 1;
int n, m, N, S, T, d[maxn];
queue<int> q;
int g[maxn][maxn];
bool mark[maxn], vis[maxn], hv[maxn];
void add_edge(int u, int v, int w)
{
// printf("%d %d %d\n", u, v, w);
edge[++tot] = node{head[u], v, w};
head[u] = tot;
edge[++tot] = node{head[v], u, 0};
head[v] = tot;
}
bool bfs(int s, int t)
{
for (int i = 1; i <= N; i++) d[i] = 0, cur[i] = head[i];
d[s] = 1;
q.push(s);
while (q.size())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edge[i].pre)
{
int v = edge[i].to;
if (edge[i].val && !d[v])
{
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[t];
}
int dinic(int u, int t, int flow)
{
if (u == t || !flow) return flow;
int res = flow;
for (int i = cur[u]; i && res; i = edge[i].pre)
{
cur[u] = i;
int v = edge[i].to;
if (edge[i].val)
{
if (d[v] == d[u] + 1)
{
int k = dinic(v, t, min(res, edge[i].val));
edge[i].val -= k;
res -= k;
edge[i ^ 1].val += k;
if (!k) d[v] = 0;
}
}
}
return flow - res;
}
int maxflow(int s, int t)
{
int res = 0;
while (bfs(s, t))
res += dinic(s, t, 0x3f3f3f3f);
return res;
}
void dfs(int u)
{
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].pre) if (!edge[i].val && edge[i].to <= 2 * n && !vis[edge[i].to]) dfs(edge[i].to);
}
int del[maxn];
int fnd(int ban = 0)
{
tot = 1;
for (int i = 1; i <= N; i++) head[i] = 0;
for (int i = 1; i <= n; i++) add_edge(S, i, 1), add_edge(i + n, T, 1);
for (int i = 1; i <= n; i++) del[i] = 0;
for (int i = 1; i <= n; i++) del[i] = i == ban || g[ban][i] || g[i][ban];
int tt = 0; for (int i = 1; i <= n; i++) if (!del[i]) tt++;
for (int i = 1; i <= n; i++) if (!del[i])
for (int j = 1; j <= n; j++) if ((i ^ j) && !del[j] && g[i][j])
add_edge(i, j + n, 1);
// puts("-------");
int res = tt - maxflow(S, T);
// printf("res = %d\n", res);
for (int i = 1; i <= 2 * n; i++) mark[i] = vis[i] = hv[i] = 0;
for (int i = head[T]; i; i = edge[i].pre) if (edge[i].val) mark[edge[i].to] = 1;
for (int i = head[S]; i; i = edge[i].pre) if (!edge[i].val) mark[edge[i].to] = 1;
for (int i = n + 1; i <= 2 * n; i++) if (!mark[i]) dfs(i);
for (int i = 1; i <= n; i++) if (!vis[i]) hv[i] = 1;
for (int i = n + 1; i <= 2 * n; i++) if (vis[i]) hv[i] = 1;
if (ban == 0)
{
printf("%d\n", res);
for (int i = 1; i <= n; i++)
{
if (!vis[i] && vis[i + n]) putchar('1');
else putchar('0');
}
puts("");
}
return res;
}
int main()
{
read(n); read(m);
N = 2 * n;
S = ++N; T = ++N;
for (int i = 1, u, v; i <= m; i++)
{
read(u); read(v);
g[u][v] = 1;
}
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];
int ans = fnd();
for (int i = 1; i <= n; i++) putchar((fnd(i) == ans - 1) + '0');
return 0;
}