Dilworth's Theorem

Definition

Partial order relation : a homogeneous relation that is transitive and antisymmetric.

Non-strict (reflexive / weak) partial order \(\le\) : Reflexivity, Antisymmetry, Transitivit.

Strict (irreflexive / strong) partial order \(<\) : Irreflexivity, Antisymmetry, Transitivit.

Converse relation (Transpose) : the relation that occurs when the order of the elements is switched.

  • the converse relation of \(\le\) is \(\ge\) , and the converse relation of \(<\) is \(>\) 。

For a partial ordered set \((A, R)\) ：

  • Chain \(A'\subseteq A\) : a totally ordered set, i.e. \(\forall x,y\in A' (x\ne y), xRy\) or \(yRx\) holds.
  • Antichain \(A'\subseteq A\) : a totally unordered set, i.e. \(\forall x,y\in A' (x\ne y),\) neither \(xRy\) nor \(yRx\) holds (incomparable).
  • Chain Decomposition (Cover) : a partition of the elements of the order into disjoint chains.

Theorem and Proof

Dilworth's Theorem

In any finite partially ordered set, the largest antichain has the same size as the smallest chaindecomposition.

The width of the partial order is defined as thecommon size of the antichain and chain decomposition.

Dual (Mirsky's theorem)

In any finite partially ordered set, the largest chain has the same size as the smallest antichain decomposition.

The depth of the partial order is defined as thecommon size of the chain and antichain decomposition.

The following proof by induction on the size of the partially ordered set \((P,\le)\).

Let \(P\) be a finite partially ordered set. The theorem holds trivially if \(P\) is empty. So, assume that \(P\) has at least one element, and let \(a\) be a maximal element of \(P\).

By induction, we assume that for some integer \(k\) the partially ordered set \(P^{\prime}:=P \backslash\{a\}\) can be covered by \(k\) disjoint chains \(C_1, \ldots, C_k\) and has at least one antichain \(A_0\) of size \(k\). Clearly, (since \(A_0\) is an antichain) , \(A_0 \cap C_i \neq \emptyset\) for \(i=1,2, \ldots, k\).

For \(i=1,2, \ldots, k\), let \(x_i\) be the maximal element in \(C_i\) that belongs to an antichain of size \(k\) in \(P^{\prime}\) , and set \(A:=\left\{x_1, x_2, \ldots, x_k\right\}\) .

  • We claim that \(A\) is an antichain. Let \(A_i\) be an antichain of size \(k\) that contains \(x_i\) . Fix arbitrary distinct indices \(i\) and \(j\) . Then \(A_i \cap C_j \neq \emptyset\) . Let \(y \in A_i \cap C_j\) . Then \(y \leq x_j\) , by the definition of \(x_j\) . This implies that \(x_i \ne x_j\) , since \(x_i \ne y\) . By interchanging the roles of \(i\) and \(j\) in this argument we also have \(x_j \ne x_i\). This verifies that \(A\) is an antichain.

We now return to \(P\). Suppose first that \(a \geq x_i\) for some \(i \in\{1,2, \ldots, k\}\). Let \(K\) be the chain \(\{a\} \cup\left\{z \in C_i: z \leq x_i\right\}\) . Then by the choice of \(x_i\) , \(P \backslash K\) does not have an antichain of size \(k\) . Induction then implies that \(P \backslash K\) can be covered by \(k-1\) disjoint chains since \(A \backslash\left\{x_i\right\}\) is an antichain of size \(k-1\) in \(P \backslash K\) . Thus, \(P\) can be covered by \(k\) disjoint chains, as required.

Next, if \(a \not\ge x_i\) for each \(i \in\{1,2, \ldots, k\}\), then \(A \cup\{a\}\) is an antichain of size \(k+1\) in \(P\) (since \(a\) is maximal in \(P\) ).

Now \(P\) can be covered by the \(k+1\) chains \(\{a\}, C_1, C_2, \ldots, C_k\), completing the proof.

Application

  1. 找二元关系并检验；2. 运用定理（及对偶定理）转化。

NOIP 1999 - 导弹拦截

给一个数列 \(a_1,a_2,\cdots,a_n\) ，问最少划分为多少个严格不增子序列。

可以接到一个序列的关系为： \(iRj=i<j\) 且 \(a_i\ge a_j\) ，容易验证该二元关系是严格偏序。

那么反链的要求即 ( \(i<j\) 且 \(a_i<a_j\) ) 或 ( \(i>j\) 且 \(a_i> a_j\) ) ，即严格上升子序列，所以答案为最长上升子序列长度。

推论：一个数列总是存在下面二者之一：一个长度为 \(\sqrt n\) 的上升子序列或一个长度为 \(\sqrt n\) 的下降子序列。

因此可以构造，每 \(\sqrt n\) 个一组，内部下降，整体上升，使得其 LIS 和 LDS 的 \(\max\) 最小。

TJOI 2015 - 组合数学

给定一个网格图，每次从左上角出发，只能往右或往下走，最后到达右下角，每个格子有最低经过次数，问最少走几次？

二元关系为向右向下走的可达性，且自己不可以到自己，是严格偏序。

求最小链覆盖，由 Dilworth 定理，等价于求最长反链，也就是两两都是严格的左下与右上的关系。

因此从左下角到右上角做最长反链的 dp 即可。设 \(f[i][j]\) 表示从左下角开始到 \((i, j)\) 的最长反链。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007

int a[N][N];

ll f[N][N];

inline void work() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) {f[i][j] = 0; a[i][j] = rd();}
    for (int i = n; i; --i)
        for (int j = 1; j <= m; ++j) 
            f[i][j] = max({f[i + 1][j], f[i][j - 1], f[i + 1][j - 1] + a[i][j]});
    printf("%lld\n", f[1][m]);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Gym 102565 - Artifact

给一张有向图 \((|V|\le 3000, |E|\le 20000)\) ，问最多选出多少个点两两不可达。

可达关系 \(iRj=\) 可以从 \(i\) 走到 \(j\) ，发现并不满足反自反性，但 SCC 缩点之后是一个DAG \((V',E')\)，满足要求。

因此求最多的点数满足两两不可达，即两两不具有 \(R\) 关系，因此所求即为 \((V',R)\) 的最长反链。

由 Dilworth 定理求偏序关系 \(R\) 的最小链覆盖 ( 注意是原图的最小可重链覆盖 )，我们有一种通用的做法：

  • 对于偏序关系 \(R\) ，用图结构表示一定是 DAG，且由传递性任意可达的两点之间距离一定为 \(1\) ；

    因此对于本题中的原图，需用传递闭包求出 \(R\) ，得到偏序关系的图表示；

  • 此时相当于求新图的最小不可重路径覆盖，即选最少的不重路径使得每个顶点恰好在一条路径中；

  • 将每个点拆成入点和出点建立二分图，对于关系中存在的 \(xRy\ (x\ne y)\) 连边：\((x_{出},y_{入})\) 。

  • 求最大匹配，证明优化目标的一致性：假设开始的时候每个点单独成链，一次匹配相当于将两个链连接起来。

  • 所以结论为最小链覆盖 = 原图顶点数 \(-\) 构造的二分图最大匹配。

此题直接 floyd 传递闭包太慢，DAG 传递闭包可以用拓扑排序更新，再用 bitset 加速复杂度为 \(O(\frac{nm}{\omega})\) 。

匹配加速可以考虑使用 Hopcroft-Karp 或 Dinic，总复杂度为 \(O(m(\frac{n}{\omega}+\sqrt n))\) 。一道类似的题。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

#define fr            first
#define sc            second
#define pb            push_back
#define mp            make_pair
#define mt            make_tuple
#define pii           pair<int, int>
#define tiii          tuple<long, long, long>
#define all(s)        (s).begin(), (s).end()
#define lowbit(x)     ((x) & -(x))
#define rep(i, x, y)  for (int (i) = (x); (i) <= (y); ++(i))
#define per(i, x, y)  for (int (i) = (x); (i) >= (y); --(i))

#define N 3007

namespace SCC {

    bool vis[N];

    int scc, bl[N];

    vector<int> e[N], re[N], nodes[N], order;

    void add(int u, int v) {e[u].push_back(v); re[v].push_back(u);}

    void dfs1(int u) {
        vis[u] = 1;
        for (auto v : e[u]) if (!vis[v]) dfs1(v);
        order.push_back(u);
    }

    void dfs2(int u) {
        nodes[bl[u] = scc].push_back(u);
        for (auto v : re[u]) if (!bl[v]) dfs2(v);
    }

    void kosaraju(int n) {
        for (int u = 1; u <= n; ++u) if (!vis[u]) dfs1(u);
        reverse(order.begin(), order.end());
        for (auto u : order) if (!bl[u]) {++scc; dfs2(u);}
    }

    int indeg[N], outdeg[N];

    vector<int> source, sink;

    unordered_map<ll, bool> valid;

    inline bool has_edge(int u, int v) {
        ll w = 1000000000ll * u + v;
        return valid[w] ? true : (valid[w] = true, 0); 
    }

    inline void shrink(int n) {
        valid.clear();
        for (int u = 1; u <= n; ++u) e[u].clear();
        for (int v = 1; v <= n; ++v)
            for (auto u : re[v]) 
                if (bl[u] != bl[v] && !has_edge(bl[u], bl[v])) {
                    ++indeg[bl[v]]; ++outdeg[bl[u]]; e[bl[u]].push_back(bl[v]);
                }
        for (int u = 1; u <= scc; ++u) if (!indeg[u]) source.push_back(u); 
        for (int u = 1; u <= scc; ++u) if (!outdeg[u]) sink.push_back(u);
        for (int u = 1; u <= n; ++u) re[u].clear();
        for (int u = 1; u <= scc; ++u) for (auto v : e[u]) re[v].push_back(u);
    }
}

namespace Hopcroft_Karp {

    const int inf = 1000000000;

    bool vis[N];
    vector<int> e[N];
    int nl, nr, ml[N], mr[N], dl[N], dr[N]; // m for match, d for distance
    
    inline bool bfs() {
        static int q[N], hd, tl; hd = 1; tl = 0;
        memset(dl, -1, sizeof(int) * (nl + 1));
        memset(dr, -1, sizeof(int) * (nr + 1));
        for (int i = 1; i <= nl; ++i) if (!ml[i]) {dl[i] = 0; q[++tl] = i;}
        int dT = inf;
        while (hd <= tl) {
            int u = q[hd++];
            if (dl[u] >= dT) break;
            for (auto v : e[u])
                if (dr[v] == -1) {
                    dr[v] = dl[u] + 1;
                    if (!mr[v]) getmin(dT, dr[v] + 1);
                    else {dl[mr[v]] = dr[v] + 1; q[++tl] = mr[v];}
                }
        }
        return dT != inf;
    }

    bool dfs(int u) {
        for (auto v : e[u]) {
            if (vis[v] || dl[u] + 1 != dr[v]) continue;
            vis[v] = true;
            if (!mr[v] || dfs(mr[v])) {mr[v] = u; ml[u] = v; return true;}
        }
        return false;
    }

    inline void add(int u, int v) {e[u].push_back(v);}

    inline int max_matching() {
        int ans = 0;
        while(bfs()) {
            memset(vis, 0, sizeof(bool) * (nr + 1));
            for (int i = 1; i <= nl; ++i) if (!ml[i]) ans += dfs(i);
        }
        return ans;
    }
}

bitset<N> edg[N];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(); SCC::add(u, v);
    }
    SCC::kosaraju(n); SCC::shrink(n); n = SCC::scc;
    // Transitive Closure   
    for (int i = n; i; --i) {
        edg[i][i] = true;
        for (auto v : SCC::e[i]) edg[i] |= edg[v];
        for (int j = i + 1; j <= n; ++j)
            if (edg[i][j]) Hopcroft_Karp::add(i, j);
    }
    Hopcroft_Karp::nl = Hopcroft_Karp::nr = n;
    printf("%d\n", n - Hopcroft_Karp::max_matching());
    return 0;
}

CTSC 2008 - 祭祀

给一个 DAG ，问：(1) 最多选出多少个点两两不可达；(2) 输出一种方案；(3) 输出每个点是否可以在某个方案中出现。

  1. DAG 直接bitset暴力传递闭包复杂度 \(\mathcal{O}(\frac{n^3}{64})=\mathcal{O}(\frac{nm}{64})\)，用 Hopcraft-Karp 复杂度 \(\mathcal{O}(m\sqrt n)=\mathcal{O}(n^{2.5})\)。

  2. 求出最长反链：按照 Konig 定理构造最小点覆盖的时候复杂度是 \(\mathcal{O}(m)\) 的，因为一个右侧点被打过标记之后，再经过他就不用管了。先找出来一个最小点覆盖，然后对于拆的点都不在最小点覆盖里的，加入最长反链。一个证明

  3. 枚举每个点，假设必选他，那么与他有偏序关系的所有点都不可以选，删掉这些之后求一下最长反链，看一下长度是否是原答案 \(-1\) 即可。

总复杂度 \(\mathcal{O}(\frac{n^3}{64} + n^2 + n\times n^{2.5})=\mathcal{O}(n^{3.5})\) ，对于 \(n=100\) 可过。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

template <const int V, const int inf = 1000000000>
struct Hopcroft_Karp {
    
    bool vis[V];
    vector<int> e[V];
    int nl, nr, ml[V], mr[V], dl[V], dr[V]; // m for match, d for distance
    
    void clear() {
        for (int i = 1; i <= nl; ++i) {ml[i] = 0; e[i].clear();}
        for (int i = 1; i <= nr; ++i) {mr[i] = 0; vis[i] = false;}
    }

    inline bool bfs() {
        static int q[V], hd, tl; hd = 1; tl = 0;
        memset(dl, -1, sizeof(int) * (nl + 1));
        memset(dr, -1, sizeof(int) * (nr + 1));
        for (int i = 1; i <= nl; ++i) if (!ml[i]) {dl[i] = 0; q[++tl] = i;}
        int dT = inf;
        while (hd <= tl) {
            int u = q[hd++];
            if (dl[u] >= dT) break;
            for (auto v : e[u])
                if (dr[v] == -1) {
                    dr[v] = dl[u] + 1;
                    if (!mr[v]) getmin(dT, dr[v] + 1);
                    else {dl[mr[v]] = dr[v] + 1; q[++tl] = mr[v];}
                }
        }
        return dT != inf;
    }

    bool dfs(int u) {
        for (auto v : e[u]) {
            if (vis[v] || dl[u] + 1 != dr[v]) continue;
            vis[v] = true;
            if (!mr[v] || dfs(mr[v])) {mr[v] = u; ml[u] = v; return true;}
        }
        return false;
    }

    inline void add(int u, int v) {e[u].push_back(v);}

    inline int max_matching() {
        int ans = 0;
        while(bfs()) {
            memset(vis, 0, sizeof(bool) * (nr + 1));
            for (int i = 1; i <= nl; ++i) if (!ml[i]) ans += dfs(i);
        }
        return ans;
    }

    bool visl[V], visr[V], anti[V];

    void addtag(int u) {
        visl[u] = true;
        for (auto v : e[u]) {
            if (visr[v]) continue;
            visr[v] = true;
            addtag(mr[v]);
        }
    }

    inline void Antichain() {
        for (int i = 1; i <= nl; ++i)
            if (!ml[i]) addtag(i);
        // visl[i] = false or visr[i] = true : vertex cover
        // visl[i] = true or visr[i] = false : independent set
        for (int i = 1; i <= nl; ++i) 
            if (visl[i] && !visr[i]) anti[i] = true;
    }
};

#define N 101

bool tag[N];

Hopcroft_Karp<N> f;

bitset<N> adj[N];

int main() {
    int n = rd(), m = rd();
    for (int i = 1, u, v; i <= m; ++i) {
        u = rd(); v = rd(); adj[u][v] = true;
    }
    for (int k = 1; k <= n; ++k)
        for (int u = 1; u <= n; ++u)
            if (adj[u][k]) adj[u] |= adj[k];
    f.nl = f.nr = n;
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v <= n; ++v) 
            if (adj[u][v]) f.add(u, v);
    int ans = n - f.max_matching();
    printf("%d\n", ans);
    f.Antichain();
    for (int i = 1; i <= n; ++i) putchar('0' + f.anti[i]); puts("");
    for (int i = 1; i <= n; ++i) {
        f.clear();
        int tot = n;
        memset(tag, 0, sizeof(tag));
        tag[i] = true; --tot;
        for (int u = 1; u <= n; ++u)
            if (adj[u][i] || adj[i][u]) {tag[u] = true; --tot;}
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v) 
                if (adj[u][v] && !tag[u] && !tag[v]) f.add(u, v);
        if (tot - f.max_matching() == ans - 1) putchar('1');
        else putchar('0'); 
    }
    return 0;
}

一些结合其他套路的题目： SPOJ - DIVREL | ABC237Ex - hakata | CF590E - Birthday.

Algorithms
Graphs

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！