题意

求一个 $n$ 点 $m$ 边的 $DAG$ 的最长反链，在第二行输出构造的其中一种方案，在第三行输出在保证最长反链的前提下，每个点是否能够设置为反链中的点

题解

反正证明也不会，就记录一下具体方法

最长反链：对 $DAG$ 点集 $V$，最长反链为一个集合 $S \subseteq V$，满足 $\forall u \in S, v \in S$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$

根据 $\text{Dilworth}$ 定理，一个 $DAG$ 的最长反链大小等于其最小可重链覆盖大小

对 $DAG$ 传递闭包后，最小可重链覆盖大小可转化为最小不可重链覆盖大小，即最小路径点覆盖

最小路径点覆盖：将 $DAG$ 用若干不相交的链覆盖，即每个点最多被经过一次，最小使用链的个数

那么最小可重链覆盖则是类似，不同之处仅在于每个点可被经过多次

最小路径点覆盖大小 $=$ $n$ $-$ 该 $DAG$ 拆点二分图的最大匹配大小

那么 $\text{Subtask1}$ 就做完了

把 $DAG$ 拆点后最小路径点覆盖就相当于是求该拆点二分图的最大独立集

接下来开始构造方案

  • 找到拆点二分图中右侧的所有非匹配点
  • 由这些非匹配点出发，右侧点只走非匹配边，左侧点只走匹配边
  • 那么一种最小点覆盖的合法方案就是取左侧中被 $DFS$ 到的点，右侧中没被 $DFS$ 到的点
  • 那么该拆点二分图的最大独立集的一种合法方案构造就是上述构造的补集

这样就求出了最小路径点覆盖的一种方案，即最长反链的一种构造

那么 $\text{Subtask2}$ 就做完了

对 $\text{Subtask3}$，枚举每个点，将它会到达的点和会到达它的点删掉，强制假如该点，再跑一遍最长反链，若其得到最长反链长度等于原答案减一，则说明该点可以被设置为反链中的点

那么 $\text{Subtask3}$ 就做完了

代码

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <queue>

using namespace std;

const int MAXN = 100 + 10;
const int MAXM = 1000 + 10;
const int MAXL = 2 * MAXN + MAXN * MAXN;

const int INF = 0x7fffffff;

int N, M;
bitset<MAXN> g[MAXN];

struct LFS { int to, cap, next; } ;
LFS Link[MAXL << 1];
int Head[MAXN << 1]= {0}, size = 1;
void Insert (int u, int v, int cap) {
	Link[++ size].to = v;
	Link[size].cap = cap;
	Link[size].next = Head[u];

	Head[u] = size;
}
void add (int x, int y, int cap) {
	Insert (x, y, cap); Insert (y, x, 0);
}

int S, T, _N;
int depth[MAXN << 1]= {0};
queue<int> que;
bool BFS () {
	while (! que.empty()) que.pop();
	memset (depth, 0, sizeof (depth));
	depth[S] = 1, que.push(S);
	while (! que.empty()) {
		int u = que.front(); que.pop();
		for (int i = Head[u]; i; i = Link[i].next) {
			int v = Link[i].to, cap = Link[i].cap;
			if (depth[v] || ! cap) continue;
			depth[v] = depth[u] + 1;
			if (v == T) return true;
			que.push(v);
		}
	}
	return false;
}
int cur[MAXL]= {0};
int Dinic (int p, int flow) {
	if (p == T) return flow;
	int rest = flow;
	for (int &i = cur[p]; i && rest; i = Link[i].next) {
		int v = Link[i].to, cap = Link[i].cap;
		if (depth[v] != depth[p] + 1 || ! cap) continue;
		int k = Dinic (v, min (cap, rest));
		if (! k) depth[v] = - 1;
		Link[i].cap -= k, Link[i ^ 1].cap += k;
		rest -= k;
	}
	return flow - rest;
}
int MAXFLOW () {
	int ret = 0;
	while (BFS ()) {
		for (int i = 1; i <= _N; i ++) cur[i] = Head[i];
		ret += Dinic (S, INF);
	}
	return ret;
}
int match[MAXN]= {0};

// Subtask2
bool tagl[MAXN]= {false}, tagr[MAXN]= {false};
void DFS (int u) {
	tagr[u - N] = true;
	for (int i = 1; i <= N; i ++)
		if (g[i][u - N] && ! tagl[i]) {
			tagl[i] = true;
			DFS (match[i]);
		}
}

//Subtask3
bool del[MAXN]= {false};

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum ();
		g[u][v] = 1;
	}
	for (int k = 1; k <= N; k ++)
		for (int i = 1; i <= N; i ++)
			if (g[i][k])
				g[i] |= g[k];
	S = 2 * N + 1, _N = T = 2 * N + 2;
	for (int i = 1; i <= N; i ++)
		add (S, i, 1), add (i + N, T, 1);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			if (g[i][j])
				add (i, j + N, 1);
	int ans = N - MAXFLOW ();
	printf ("%d\n", ans);
	for (int i = 1; i <= N; i ++)
		if (! Link[4 * i - 2].cap)
			for (int j = Head[i]; j; j = Link[j].next)
				if (! Link[j].cap) {
					match[i] = Link[j].to;
					break;
				}
	for (int i = 1; i <= N; i ++)
		if (Link[4 * i].cap)
			DFS (i + N);
	for (int i = 1; i <= N; i ++) printf ("%d", ! tagl[i] && tagr[i]);
	puts ("");
	for (int i = 1; i <= N; i ++) {
		memset (Head, 0, sizeof (Head)); size = 1;
		memset (del, false, sizeof (del));
		for (int j = 1; j <= N; j ++)
			if (i == j || g[i][j] || g[j][i])
				del[j] = true;
		int m = 0;
		for (int i = 1; i <= N; i ++)
			if (! del[i]) {
				add (S, i, 1), add (i + N, T, 1);
				m ++;
			}
		for (int i = 1; i <= N; i ++)
			if (! del[i])
				for (int j = 1; j <= N; j ++)
					if (g[i][j] && ! del[j])
						add (i, j + N, 1);
		int ret = m - MAXFLOW ();
		printf ("%d", ret == ans - 1);
	}
	puts("");

	return 0;
}