「BZOJ 1143/2718」毕业旅行-Dilworth 定理

一个 $n$ 个点 $m$ 条边的有向图,求最多能选择多少个点,使得任意两点不连通。

链接

BZOJ 1143
BZOJ 2718

题解

Dilworth 定理:
设 $(X, \leq)$ 是有限偏序集,并设 $m$ 是反链的最大大小,则 $X$ 可以被划分成 $m$ 个链,但不能划分成少于 $m$ 个链。

题目中的图即为由连通关系确定的有限偏序集,故最长反链为最小链覆盖。

类似二分图的最小路径覆盖,这里我们先用 Floyd 传递闭包,求出任意两点间的连通性,然后以连通性为条件建图跑二分图最大匹配即可。

时间复杂度 $O(\frac {n ^ 3} {w} + \mathrm{maxflow}(n, m))$。

代码

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
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「BZOJ 2718」毕业旅行 03-03-2018
* Dilworth 定理
* @author xehoth
*/
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
template <size_t MAXN, int INF = 0x3f3f3f3f>
struct Maxflow {
struct Node {
int v, f, i;
Node(int v, int f, int i) : v(v), f(f), i(i) {}
};
std::vector<Node> g[MAXN];
inline void addEdge(int u, int v, int f) {
g[u].push_back(Node(v, f, g[v].size()));
g[v].push_back(Node(u, 0, g[u].size() - 1));
}
typedef typename std::vector<Node>::iterator Iterator;
int s, t, n;
bool vis[MAXN];
int h[MAXN], gap[MAXN], iter[MAXN];
inline void bfs() {
static std::queue<int> q;
q.push(t);
vis[t] = true;
gap[0]++;
for (int u; !q.empty();) {
u = q.front();
q.pop();
for (Iterator p = g[u].begin(); p != g[u].end(); ++p) {
if (!vis[p->v]) {
gap[h[p->v] = h[u] + 1]++;
vis[p->v] = true;
q.push(p->v);
}
}
}
}
int dfs(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int &i = iter[u]; i < (int)g[u].size(); i++) {
Node &p = g[u][i];
if (p.f > 0 && h[u] == h[p.v] + 1) {
int t = dfs(p.v, std::min(flow - ret, p.f));
p.f -= t;
g[p.v][p.i].f += t;
if ((ret += t) == flow || h[s] >= n) return ret;
}
}
if (--gap[h[u]] == 0) h[s] = n;
gap[++h[u]]++;
iter[u] = 0;
return ret;
}
inline int maxflow(int s, int t, int n) {
this->s = s;
this->t = t;
this->n = n;
int ret = 0;
for (bfs(); h[s] < n;) {
memset(iter, 0, sizeof(int) * n);
ret += dfs(s, INF);
}
return ret;
}
};
const int MAXN = 200 + 1;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int n, m;
std::cin >> n >> m;
static std::bitset<MAXN> f[MAXN];
static Maxflow<MAXN * 2 + 1> g;
for (int i = 0, u, v; i < m; i++) {
std::cin >> u >> v;
f[u].set(v);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
if (f[i].test(k)) f[i] |= f[k];
const int S = 0, T = 2 * n + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (f[i].test(j)) g.addEdge(i, j + n, 1);
for (int i = 1; i <= n; i++) {
g.addEdge(S, i, 1);
g.addEdge(i + n, T, 1);
}
std::cout << n - g.maxflow(S, T, T + 1);
return 0;
}
分享到