给定一个\(n\)个点,\(m\)条边的有向无环图(\(DAG\)),求最多能选多少个点使得它们两两之间不能到达,并且要求你构造出一种方案,且判断每个点是否有可能被选出
\(n \leq 100\),\(m \leq 1000\)
在一个\(DAG\)中,它的最长反链就是选出一个点集,使得它们两两之间不能到达,并且使这个点集最大
题目中有三个问题
最多能选多少个点使得它们两两之间不能到达,即求这个\(DAG\)的最长反链为多大
根据\(Dilworth\)定理,一个\(DAG\)的最长反链的大小和最小可重链覆盖大小相等。
问题转换成求这个\(DAG\)的最小可重链覆盖的大小
求\(DAG\)最小可重链覆盖的大小,可以先以\(\mathcal O(\frac{n^3}{64})\)的复杂度求出它的传递闭包,再转换成求二分图的最小不可重链覆盖
具体地,我们建一个二分图,左边有\(n\)个节点,右边也有\(n\)个节点,不妨设左边第\(i\)个节点为\(a_i\),右边第\(i\)个节点为\(b_i\)
对于\(DAG\)中,\(u\)能到达\(v\),那么我们在\(a_u\)个\(b_v\)之间连一条边
根据二分图上,最小不可重链覆盖大小等于点数减去最大匹配大小,可以网络流求二分图的最大匹配,由于边数是\(n^2\)级别的,所以这部分的复杂度是\(\mathcal O(n^2\sqrt{n})\)
构造一组方案
考虑二分图上的最大独立集和\(DAG\)中的最长反链之间的关系
令二分图上最大匹配的大小为\(X\),则最大独立集的大小就为\(2n-X\),对于\(a_i\)和\(b_i\)均在最大独立集的点\(i\),它们全部取出来可以构成\(DAG\)的一条反链
假设对于一个最大独立集,我们将\(a_i\)和\(b_i\)均在最大独立集的点\(i\)全部取出来,记个数为\(t\),由于最长反链的大小为\(n-X\),所以\(t \leq n-X\)
则剩下最大独立集中的点数为\(2n-X-t \geq 2n-X-(n-X)=n\),又独立的点最多就\(n\)个,所以\(2n-X-t \leq n\),故\(2n-X-t=n\),所以\(t = n - X\)
所以我们只需要任意找到一组二分图上的最大独立集,就能找出\(DAG\)的一个最长反链
现在问题转换为求出一组二分图的最大独立集
又由于二分图上最大独立集与最小点覆盖互补,求出一组最小点覆盖即可
找出一组最小点覆盖,在找到一组最大匹配的基础上,我们可以从右边的非匹配点开始\(dfs\),每次从右边走非匹配边到左边,然后从左边走匹配边到右边,然后取左边被\(dfs\)到的点和右边没有被\(dfs\)到的点可以组成一组最小点覆盖
证明:
最大独立集与最小点覆盖互补,即取左边没有被\(dfs\)到的点和右边被\(dfs\)到的点
所以最长反链就是取所有\(a_i\)没有被\(dfs\)到且\(b_i\)被\(dfs\)到的点\(i\)
由于每个点只会被遍历一次,所以这部分的时间复杂度是\(\mathcal O(n)\)的
判断每个点是否可能存在于最长反链中
对于每个点,假设它存在于最长反链中,那么在这个\(DAG\)中,能到达它的点和它能到达的点都不会存在于这个最长反链中,将这些点全部删去,判断剩下的点构成的最长反链长度是否为原先得到的答案减\(1\)
时间复杂度为\(\mathcal O(n^3 \sqrt{n})\)
总的时间复杂度为\(\mathcal O(n^3 \sqrt{n})\)
#include<bits/stdc++.h> using namespace std; #define Re register int const int N = 205, M = 20405; int n, m, t, cnt = 1, ans, l, r, hea[N], h[N], nxt[M], to[M], d[N], q[N]; bool wi[M], p[N], pp[N], b[N]; bitset<N> bt[N]; inline int read() { char c = getchar(); int ans = 0; while (c < 48 || c > 57) c = getchar(); while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar(); return ans; } inline void add(int x, int y) { nxt[++cnt] = hea[x], to[cnt] = y, wi[cnt] = 1, hea[x] = cnt; nxt[++cnt] = hea[y], to[cnt] = x, hea[y] = cnt; } inline bool bfs() { for (Re i = 0; i <= t; ++i) h[i] = hea[i], d[i] = 0; d[l = r = 0] = 1; while (l <= r) { int x = q[l++]; for (Re i = hea[x]; i; i = nxt[i]) { int u = to[i]; if (b[u] || !wi[i] || d[u]) continue; d[q[++r] = u] = d[x] + 1; if (u == t) return 1; } } return 0; } inline int dinic(int x, int y) { if (x == t) return y; int res = y; for (Re &i = h[x]; i; i = nxt[i]) { int u = to[i]; if (!wi[i] || d[u] ^ d[x] + 1) continue; bool v = dinic(u, min(res, 1)); if (v) { wi[i] = 0, wi[i ^ 1] = 1, --res; if (!res) return y; } } return y - res; } inline void dfs(int x) { p[x] = 1; for (Re i = hea[x]; i; i = nxt[i]) if (to[i] && to[i] < t && !wi[i] && !p[to[i]]) dfs(to[i]); } int main() { n = ans = read(), m = read(), t = n << 1 | 1; for (Re i = 1; i <= n; ++i) add(0, i), add(n + i, t); for (Re i = 0; i < m; ++i) { int u = read(), v = read(); bt[u][v] = 1; } for (Re i = 1; i <= n; ++i) for (Re j = 1; j <= n; ++j) if (bt[j][i]) bt[j] |= bt[i]; for (Re i = 1; i <= n; ++i) for (Re j = 1; j <= n; ++j) if (bt[i][j]) add(i, n + j); int fl; while (bfs()) while (fl = dinic(0, n)) ans -= fl; printf("%d\n", ans); for (Re i = hea[t]; i; i = nxt[i]) if (!wi[i] && !p[to[i]]) dfs(to[i]); for (Re i = 1; i <= n; ++i) if (!p[i] && p[n + i]) pp[i] = 1; for (Re i = 1; i <= n; ++i) putchar(48 + pp[i]); putchar('\n'); for (Re i = 1; i <= n; ++i) if (!pp[i]) { int s = n - 1; b[i] = b[n + i] = 1; for (Re j = 1; j <= n; ++j) if (bt[i][j] | bt[j][i]) b[j] = b[n + j] = 1, --s; for (Re j = 2; j < cnt; j += 2) wi[j] = 1, wi[j ^ 1] = 0; while (bfs()) while (fl = dinic(0, n)) s -= fl; pp[i] = (s == ans - 1), b[i] = b[n + i] = 0; for (Re j = 1; j <= n; ++j) if (bt[i][j] | bt[j][i]) b[j] = b[n + j] = 0; } for (Re i = 1; i <= n; ++i) putchar(48 + pp[i]); return 0; }