跳转至

二分图

对于图 \(G=(V,E)\)，如果存在 \(V\) 的一种黑白染色方案 \(c_i\)，满足 \(\forall (u,v)\in E,\ c_u\ne c_v\)，则称图 \(G\) 为二分图。

最大匹配

对于二分图边集的一个子集 \(E'\)，如果不存在两条边具有公共顶点，则称 \(E'\) 为二分图 \(G\) 的一个匹配。最大化 \(|E'|\) 的问题叫做最大匹配。

最大匹配问题可以使用网络流建模：

二分图匹配

其中两侧的蓝点分别对应二分图的两个点集，中间橙色的边对应二分图的边（橙色边的边权可以是 \(1\)，但是为了方便理解后面的最小点覆盖，我们将其赋为 \(+\infty\)，显然也不会影响时间复杂度）。正确性显然。

于是我们可以使用 Dinic 解决二分图最大匹配问题，时间复杂度 \(O(m\sqrt m)\)。

Dinic 代码 
 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
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e7 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w, next;
} pool[2 * M + 4 * N];
int ne = 1, head[2 * N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
    pool[++ne] = {u, 0, head[v]};
    head[v] = ne;
}

int n, m, s, t;

namespace dinic {
    int que[2 * N], hd, tl;
    int dep[2 * N], now[2 * N];
    bool bfs() {
        for(int i = 1; i <= t; i++) dep[i] = 0;
        for(int i = 1; i <= t; i++) now[i] = head[i];
        dep[s] = 1;
        hd = 1, tl = 0;
        que[++tl] = s;
        while(hd <= tl) {
            int u = que[hd++];
            if(u == t) return true;
            for(int i = head[u]; i; i = pool[i].next) {
                int v = pool[i].v, w = pool[i].w;
                if(!w || dep[v]) continue;
                dep[v] = dep[u] + 1;
                que[++tl] = v;
            }
        }
        return false;
    }
    int dfs(int u, int sum) {
        if(u == t) return sum;
        int flow = 0;
        for(int i = now[u]; i && sum; i = pool[i].next) {
            now[u] = i;
            int v = pool[i].v, w = pool[i].w;
            if(dep[v] != dep[u] + 1 || !w) continue;
            int k = dfs(v, min(sum, w));
            if(!k) {
                dep[v] = 0;
            } else {
                pool[i].w -= k;
                pool[i ^ 1].w += k;
                flow += k;
                sum -= k;
            }
        }
        return flow;
    }
    int calc() {
        int flow = 0;
        while(bfs()) flow += dfs(s, INF);
        return flow;
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v + N, 1);
    }

    s = 2 * N - 5;
    t = s + 1;

    for(int i = 1; i <= n; i++) addEdge(s, i, 1);
    for(int i = 1; i <= n; i++) addEdge(i + N, t, 1);

    cout << dinic::calc() << '\n';

    return 0;
}

其实，我们还有一种暴力寻找增广路的算法：匈牙利算法。它使用 dfs 寻找图上的增广路。其时间复杂度上界是 \(O(nm)\)，在随机稠密图上跑得飞快（因为增广路很短，无需一遍 \(O(m)\) 的 bfs，因此比 Dinic 快），在特殊的稠密图上可以被卡（没有 Dinic 快）。

匈牙利 代码 
 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
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e7 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, next;
} pool[M];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m, ans;

int link[N], vis[N];

bool dfs(int u) {
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        if(!link[v] || dfs(link[v])) {
            link[v] = u;
            return true;
        }
    }
    return false;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }

    for(int i = 1; i <= n; i++) {
        ans += dfs(i);
        for(int j = 1; j <= n; j++) vis[j] = 0;
    }

    cout << ans << '\n';

    return 0;
}
卡匈牙利

通过将 dfs 引向之前已经匹配好的区域，可以使增广路不会太短。

gen.cpp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include "testlib.h"
using namespace std;

int n = 3162;
int m = n * n;

int main() {

    cout << n << ' ' << m << '\n';
    // 随机稠密图
    // for(int i = 1; i <= m; i++) {
    //     cout << gen(1, n) << ' ' << gen(1, n) << '\n';
    // }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cout << i << ' ' << j << '\n';
        }
    }

    return 0;
}

最大独立集，最小点覆盖

引理

二分图最大独立集的补集是最小点覆盖。

证明

考虑每条边至多有一个端点在最大独立集内；取反后，每条边至少有一个端点在最小点覆盖内。因此独立集的补集显然是点覆盖，最大独立集的补集就是最小点覆盖。

Konig 定理

二分图最小点覆盖等于最大匹配。

证明

考虑最大匹配的建模：

二分图匹配

原图中每一条边都对应一条容量为 \(+\infty\) 的边。当且仅当一条橙色边上面有流量，它包含于最大匹配。正确性显然。

我们尝试用这个模型求出最小点覆盖。对于节点 \(u\)，如果它和 \(s,t\) 之间的一条连边被割断了，则它出现在点覆盖集合中。显然，不会出现一条橙色边的两端同时没有出现在点覆盖中。并且，点覆盖的大小等于割边的数量。

根据最大流最小割定理，在二分图上，最大匹配等于最小点覆盖。

根据这两条结论，我们就可以求出二分图的最小点覆盖和最大独立集。

Y12-2 攻击装置

给定一个 \(n\times n\) 的棋盘，有些位置有障碍物。问你最多可以在棋盘上摆放多少个“马”的棋子，使得棋子两两之间不能直接攻击到。

\(n\le 200\)

注意到仍然可以给棋盘进行黑白染色，问题转化为二分图最大独立集。直接网络流即可。时间复杂度 \(O(8n^3)\)。

代码 
  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
#include<iostream>
using namespace std;
const int N = 210 * 210;
const int INF = 0x3f3f3f3f;
const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

struct Edge {
    int v, w, next;
} pool[2 * 8 * N + 2 * 2 * N];
int ne = 1, head[N];

inline void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
    pool[++ne] = {u, 0, head[v]};
    head[v] = ne;
}

int n, s, t, ans;
int ban[N];

inline bool in_bound(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= n;
}

inline int g(int x, int y) { return (x - 1) * n + y; }
inline int gx(int p) { return (p - 1) / n + 1; }
inline int gy(int p) { return (p - 1) % n + 1; }

namespace Dinic {
    int now[N], dep[N];
    int que[N], hd, tl;
    bool bfs() {
        for(int i = 1; i <= t; i++) now[i] = head[i];
        for(int i = 1; i <= t; i++) dep[i] = 0;
        hd = 1, tl = 0;
        que[++tl] = s;
        dep[s] = 1;
        while(hd <= tl) {
            int u = que[hd++];
            if(u == t) return true;
            for(int i = head[u]; i; i = pool[i].next) {
                int v = pool[i].v, w = pool[i].w;
                if(!w) continue;
                if(dep[v]) continue;
                dep[v] = dep[u] + 1;
                que[++tl] = v;
            }
        }
        return false;
    }
    int dfs(int u, int sum) {
        if(u == t) return sum;
        int flow = 0;
        for(int i = now[u]; i && sum; i = pool[i].next) {
            int v = pool[i].v, w = pool[i].w;
            now[u] = i;
            if(!w || dep[v] != dep[u] + 1) continue;
            int cur = dfs(v, min(w, sum));
            if(!cur) dep[v] = 0;
            else {
                pool[i].w -= cur;
                pool[i ^ 1].w += cur;
                sum -= cur;
                flow += cur;
            }
        }
        return flow;
    }
    int calc() {
        int flow = 0;
        while(bfs()) flow += dfs(s, INF);
        return flow;
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            char c;
            cin >> c;
            ban[g(i, j)] = c == '1';
            ans += c == '0';
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int p = g(i, j);
            if(ban[p] || (i + j) & 1) continue;
            for(int d = 0; d < 8; d++) {
                int ii = i + dx[d];
                int jj = j + dy[d];
                int q = g(ii, jj);
                if(!in_bound(ii, jj) || ban[q]) continue;
                addEdge(p, q, 1);
            }
        }
    }

    s = n * n + 1;
    t = s + 1;

    for(int i = 1; i <= n * n; i++) {
        if((gx(i) + gy(i)) & 1) addEdge(i, t, 1);
        else addEdge(s, i, 1);
    }

    cout << (ans - Dinic::calc()) << endl;

    return 0;
}

P3231 [HNOI2013] 消毒

给定一个 \(n\times m\times h\) 的立方体（\(n,m,h\in \N^*\)）；立方体被分成了 \(nmh\) 个 \(1\times 1\times 1\) 的小立方体。有一些小立方体是被点亮的。每次你可以选择一个厚度为 \(1\) 的区域（不限制朝向），将区域内的所有小方块全部熄灭（可以重复熄灭）。问最少操作多少次。

\(nmh\le 5000\)

注意到 \(\min\{n,m,h\}\le 17\)。我们可以找出 \(\le 17\) 的一维（不妨设为 \(h\) 维度），枚举这一维的操作（\(2^{17}\)），然后对另外两维跑最小点覆盖。

由于匈牙利在稠密图上跑得飞快，因此我们使用匈牙利。

匈牙利 代码

注意不要每次都重新建图，这样会很慢。可以给每条边记一个边权表示它在 \(h\) 维度的坐标。每次最小点覆盖的时候只选择没有被删掉的边即可。

  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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 5010;
const int N2 = 19;
const int INF = 0x3f3f3f3f;

struct myPair {
    int x, y;
    inline bool operator<(const myPair &b) const {
        if(x != b.x) return x < b.x;
        return y < b.y;
    }
    inline bool operator==(const myPair &b) const {
        return x == b.x && y == b.y;
    }
};

int T;
int n, m, h;
int ans;

struct Edge {
    int v, w, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

void clear() {
    memset(head, 0, sizeof(head));
    ne = 0;
}

int ban[N2];

namespace Hun {

    int n, m;
    int vis[N], link[N];

    int now;
    bool dfs(int u) {
        for(int i = head[u]; i; i = pool[i].next) {
            if(ban[pool[i].w]) continue;
            int v = pool[i].v;
            if(vis[v] == now) continue;
            vis[v] = now;
            if(!link[v] || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
        return false;
    }

    int calc() {
        for(int i = 1; i <= m; i++) link[i] = 0;
        int ans = 0;
        now = 0;
        for(int i = 1; i <= m; i++) vis[i] = 0;
        for(int i = 1; i <= n; i++) {
            ++now;
            ans += dfs(i);
        }
        return ans;
    }

}

int main() {

    cin >> T;

    while(T--) {
        clear();
        {
            int tmp;
            cin >> n >> m >> h;
            if(n <= 17) tmp = 0;
            else if(m <= 17) tmp = 1;
            else tmp = 2;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    for(int k = 1; k <= h; k++) {
                        int x;
                        cin >> x;
                        if(x) {
                            if(tmp == 0) addEdge(j, k, i);
                            if(tmp == 1) addEdge(i, k, j);
                            if(tmp == 2) addEdge(i, j, k);
                        }
                    }
                }
            }
            if(tmp == 0) swap(n, h);
            if(tmp == 1) swap(m, h);
        }
        Hun::n = n;
        Hun::m = m;
        ans = INF;
        for(int i = 0; i < (1 << h); i++) {
            int res = __builtin_popcount(i);
            for(int j = 0; j < h; j++) {
                ban[j + 1] = (bool)(i & (1 << j));
            }
            ans = min(ans, res + Hun::calc());
        }
        cout << ans << '\n';
    }

    return 0;
}

这里也提供一份 Dinic 代码。

Dinic 代码 
  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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 5010;
const int N2 = 19;
const int INF = 0x3f3f3f3f;

struct myPair {
    int x, y;
    inline bool operator<(const myPair &b) const {
        if(x != b.x) return x < b.x;
        return y < b.y;
    }
    inline bool operator==(const myPair &b) const {
        return x == b.x && y == b.y;
    }
};

int T;
int n, m, h;
int ans;

vector<myPair> pt[N2];
vector<myPair> par;

void clear() {
    for(int i = 0; i <= 18; i++) pt[i].clear();
}

namespace Dinic {

    int n, m, s, t;

    struct Edge {
        int v, c, next;
    } pool[4 * N];
    int ne, head[N];

    void addEdge(int u, int v, int c) {
        pool[++ne] = {v, c, head[u]};
        head[u] = ne;
        pool[++ne] = {u, 0, head[v]};
        head[v] = ne;
    }

    void init(int _n, int _m) {
        n = _n, m = _m;
        s = n + m + 1;
        t = s + 1;
        for(int i = 1; i <= t; i++) head[i] = 0;
        ne = 1;
        for(int i = 1; i <= n; i++) addEdge(s, i, 1);
        for(int i = n + 1; i <= n + m; i++) addEdge(i, t, 1);
    }

    void insert(int x, int y) {
        addEdge(x, y + n, 1);
    }

    int dep[N], now[N];
    int que[N], hd, tl;

    bool bfs() {
        for(int i = 1; i <= t; i++) now[i] = head[i];
        for(int i = 1; i <= t; i++) dep[i] = 0;
        dep[s] = 1;
        hd = 1, tl = 0;
        que[++tl] = s;
        while(hd <= tl) {
            int u = que[hd++];
            if(u == t) return true;
            for(int i = head[u]; i; i = pool[i].next) {
                int v = pool[i].v, c = pool[i].c;
                if(!c || dep[v]) continue;
                dep[v] = dep[u] + 1;
                que[++tl] = v;
            }
        }
        return false;
    }

    int dfs(int u, int sum) {
        if(u == t) return sum;
        int flow = 0;
        for(int i = now[u]; i && sum; i = pool[i].next) {
            now[u] = i;
            int v = pool[i].v, c = pool[i].c;
            if(!c || dep[v] != dep[u] + 1) continue;
            int k = dfs(v, min(c, sum));
            if(k == 0) dep[v] = 0;
            else {
                pool[i].c -= k;
                pool[i ^ 1].c += k;
                sum -= k;
                flow += k;
            }
        }
        return flow;
    }

    int calc() {
        int ans = 0;
        while(bfs()) ans += dfs(s, INF);
        return ans;
    }

}

int calc() {
    Dinic::init(n, m);
    sort(par.begin(), par.end());
    auto tail = unique(par.begin(), par.end());
    while(par.end() != tail) par.pop_back();
    for(myPair &p : par) {
        Dinic::insert(p.x, p.y);
    }
    return Dinic::calc();
}

int main() {

    cin >> T;

    while(T--) {
        clear();
        {
            int tmp;
            cin >> n >> m >> h;
            if(n <= 17) tmp = 0;
            else if(m <= 17) tmp = 1;
            else tmp = 2;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    for(int k = 1; k <= h; k++) {
                        int x;
                        cin >> x;
                        if(x) {
                            if(tmp == 0) pt[i].push_back({j, k});
                            if(tmp == 1) pt[j].push_back({i, k});
                            if(tmp == 2) pt[k].push_back({i, j});
                        }
                    }
                }
            }
            if(tmp == 0) swap(n, h);
            if(tmp == 1) swap(m, h);
        }
        ans = INF;
        for(int i = 0; i < (1 << h); i++) {
            par.clear();
            int res = 0;
            for(int j = 1; j <= h; j++) {
                if(!(i & (1 << (j - 1)))) {
                    for(myPair &p : pt[j]) {
                        par.push_back(p);
                    }
                } else ++res;
            }
            ans = min(ans, res + calc());
        }
        cout << ans << '\n';
    }

    return 0;
}

Y12-4 游戏

有一个 \(n\times m\) 的网格图，网格图上的一些位置存在障碍。

Alice 和 Bob 在网格图上博弈：Alice 先指定一个位置（不能是障碍），放置一个棋子；接着，Alice 和 Bob 轮流移动棋子，将棋子移动到 \(4\) 连通区域内的任意一个点（也不能是障碍）；同一个位置不能被棋子经过两次，不能移动者判负。

问 Alice 是否有必胜策略，以及第一步可以将棋子放在哪些位置。

\(n,m\le 100\)

先将网格图转换为一个二分图，原问题转化为二分图上的博弈。

先考虑一种特殊情况：二分图存在一个完美匹配。那么 Bob 只需要一直沿着匹配边走，Alice 就不能走匹配边，最终一定是 Alice 走不动；因此 Bob 一定获胜。

考虑其它情况：图不存在完美匹配。如果 Alice 选择一个匹配点，则 Alice 有可能在被 Bob 堵截的过程中走到一个未匹配点。考虑此时的局势，容易发现 Bob 不可能再走到一个未匹配点，否则匹配不是最大的。此时，Alice 只需要沿着匹配边走就可以了，Alice 胜。

进一步的，如果 Alice 初始就选择一个未匹配点，则 Alice 必胜。因此，如果图存在完美匹配，则 Bob 必胜，否则 Alice 必胜。

另外，我们应该讨论最大匹配不唯一的情况。对于 Bob 必胜的情况，Bob 只需要任意选择一个完美匹配就可以。对于 Alice 必胜的情况，Alice 也可以任意选择一个匹配，不会影响 Bob 必输的结果；因此，对于节点 \(u\)，只要存在一个最大匹配不包含 \(u\)，那么选择 \(u\) 就是必胜的。

如果一个节点 \(u\) 不一定在最大匹配中，称 \(u\) 为“非必需点”。我们希望找出所有非必需点。

我们先随便找一个最大匹配 \(M\)，找出所有不在 \(M\) 中的节点作为初始的非必需点。容易发现，以一个非必需点 \(x\) 为根的交错树中与 \(x\) 同侧的节点都是非必需点。通过 \(|V|\) 次 dfs 即可求出；通过 vis 数组的优化可以做到 \(O\big(|V|+|E|\big)\)。

时间复杂度 \(O\big(4(nm)^2+nm\big)\)，跑得飞快。

代码 
  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
#include<iostream>
#include<vector>
#define print(x) (cout << gx(x) << ' ' << gy(x) << '\n')
#define print1(x) (cout << gx(x) << ' ' << gy(x) << "  ")

using namespace std;
const int N = 105;

struct Edge {
    int v, next;
} pool[2 * 4 * N * N];
int ne, head[N * N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
    pool[++ne] = {u, head[v]};
    head[v] = ne;
}

int n, m;
int ban[N][N];

inline int g(int x, int y) { return x * m + y; }
inline int gx(int x) { return (x - 1) / m; }
inline int gy(int x) { return (x - 1) % m + 1; }

inline bool in_bound(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m && !ban[x][y];
}

int vis[N * N];
int link[N * N];

bool KM(int u) {
    if(vis[u]) return false;
    vis[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(!link[v] || KM(link[v])) {
            link[v] = u;
            return true;
        }
    }
    return false;
}

bool match[N * N];

void dfs(int u) {
    if(vis[u]) return;
    match[u] = 0;
    vis[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(link[v]) dfs(link[v]);
    }
}

vector<int> ans;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            ban[i][j] = c == '#';
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if((i + j) & 1) continue;
            if(ban[i][j]) continue;
            if(in_bound(i - 1, j)) addEdge(g(i, j), g(i - 1, j));
            if(in_bound(i + 1, j)) addEdge(g(i, j), g(i + 1, j));
            if(in_bound(i, j - 1)) addEdge(g(i, j), g(i, j - 1));
            if(in_bound(i, j + 1)) addEdge(g(i, j), g(i, j + 1));
        }
    }

    for(int i = m + 1; i <= n * m + m; i++) {
        if(ban[gx(i)][gy(i)]) continue;
        if((gx(i) + gy(i)) & 1) continue;
        KM(i);
        for(int j = m + 1; j <= n * m + m; j++) vis[j] = 0;
    }

    for(int i = m + 1; i <= n * m + m; i++) {
        if(!link[i]) continue;
        match[i] = match[link[i]] = 1;
        link[link[i]] = i;
    }

    for(int i = m + 1; i <= n * m + m; i++) {
        if(match[i]) continue;
        if(ban[gx(i)][gy(i)]) continue;
        dfs(i);
    }

    for(int i = m + 1; i <= n * m + m; i++) {
        if(ban[gx(i)][gy(i)]) continue;
        if(!match[i]) ans.push_back(i);
    }

    cout << (ans.size() ? "WIN\n" : "LOSE\n");
    for(int i : ans) print(i);

    return 0;
}

二分图完美匹配 & Hall 定理

对于一个二分图，如果存在一个匹配完整覆盖了一侧的所有点，就称这个匹配是这一侧点的完美匹配。

Hall 定理

二分图 \((V_1,V_2,E)\)（不妨设 \(|V_1|\le |V_2|\)）存在 \(V_1\) 的完美匹配的充要条件是，对于所有 \(V_1\) 的子集 \(S\) 都有 \(|c(S)|\ge |S|\)。

其中 \(c(S)\) 表示 \(S\) 的陪集 \(\bigcup_{u\in S} to(u)\)，即所有与 \(S\) 中节点直接连接的右侧点组成的集合。

推广 1

二分图 \((V_1,V_2,E)\) 存在大小为 \(|V_1|-k\) 的匹配的充要条件是，对于所有 \(V_1\) 的子集 \(S\) 都有 \(|c(S)|+k\ge |S|\)。

证明可以看这篇文章。

CF468D Tree

给定一棵大小为 \(n\) 的无根树，你需要构造一个长度为 \(n\) 的 \(1\sim n\) 的排列 \(p\)，使 \(\sum_{i=1}^{n}dis(i,p_i)\) 最大。并给出字典序最小的构造方案。

\(n\le 10^5\)

首先我们任意钦定一个根节点 \(rt\)，记节点 \(i\) 到根的距离为 \(d(i)\)，那么上式可以表示为 \(\sum_{i=1}^{n}2d(i)-\sum_{i=1}^{n}d(\operatorname{lca}(i,p_i))\)。并且不难说明这个式子的最小值不随根节点而改变。在固定一个根节点之后，式子的第一项不变，第二项有最大值 \(0\)，由此推出答案不能超过 \(\sum_{i=1}^{n}2d(i)\) 的最小值。

\(\sum_{i=1}^{n}2d(i)\) 在 \(rt\) 是重心时取最小值，此时尝试将第二项构造为 \(0\)。问题转化为：给定若干组元素，你需要将元素配对，使得每一对的两个元素都不在同一组中（配对是单向的）。

结论：上面这个问题，在每组元素数量不存在绝对众数时有解；

如果存在绝对众数，那么显然无解。否则，找到最大的两个组，各取一个元素进行匹配（双向匹配），仍然满足条件。发现当 \(rt\) 是重心时，各子树大小显然都不超过 \(\lceil\frac{n}{2}\rceil\)，因此不存在绝对众数，因而一定有解，答案可以取到上界 \(\sum_{i=1}^{n}d(i)\)。

那么如何构造使得字典序最小呢？考虑贪心处理，问题转化为判定一次单向匹配之后是否仍然有解。而这里产生的子问题是上面问题的强化版，可以刻画为一个二分图匹配问题：左部点和右部点各分为 \(k\) 组，当两个点 \(i,j\) 所在组的编号不同时，二者之间连一条边。那么根据霍尔定理，局面有解当且仅当对任意 \(i\in[1,k]\)，左右两边的第 \(i\) 组大小之和不超过节点数 \(n\)（二分图点数的一半）。

因此每次匹配先检查是否有一组节点数之和超过了 \(n\)，若是则强制匹配到这一组；否则找到全局最小值进行匹配。这里可以用堆维护全局抠掉一个点之后的答案。注意 \(rt\) 可以和自己进行匹配，这里注意特判。

代码 
  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
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, rt;
int dfn[N], id[N], dt;
int mxp[N], szt[N], anc[N];
int son[N], nn;
ll d[N], sum;

void dfs1(int u, int fa) {
    szt[u] = 1;
    dfn[u] = ++dt;
    id[dt] = u;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        szt[u] += szt[v];
        mxp[u] = max(mxp[u], szt[v]);
    }
    mxp[u] = max(mxp[u], n - szt[u]);
    if(mxp[u] < mxp[rt]) rt = u;
}

void dfs2(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        d[v] = d[u] + w;
        if(!anc[u]) { son[++nn] = v; anc[v] = nn; }
        else anc[v] = anc[u];
        dfs2(v, u);
    }
}

template<typename _Tp>
struct myHeap {
    priority_queue<_Tp, vector<_Tp>, greater<_Tp> > que, del;
    inline void push(_Tp x) { que.push(x); }
    inline void erase(_Tp x) { del.push(x); }
    inline _Tp top() {
        while(!del.empty() && que.top() == del.top()) { que.pop(), del.pop(); }
        return que.top();
    }
    inline bool empty() { return que.size() == del.size(); }
    inline _Tp top(int eid) {
        if(eid == nn || top().id != eid) return top();
        _Tp tmp = top();
        que.pop();
        _Tp res = top();
        que.push(tmp);
        return res;
    }
};

struct Node1 {
    int id, mn;
    inline bool operator>(const Node1 &b) const { if(mn != b.mn) return mn > b.mn; return id > b.id; }
    inline bool operator==(const Node1 &b) const { return mn == b.mn && id == b.id; }
};

struct Node2 {
    int id, sz;
    inline bool operator>(const Node2 &b) const { if(sz != b.sz) return sz < b.sz; return id > b.id; }
    inline bool operator==(const Node2 &b) const { return sz == b.sz && id == b.id; }
};

priority_queue<int, vector<int>, greater<int> > pt[N];
myHeap<Node1> mn;
myHeap<Node2> sz;
int cs[N];

int ans[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    mxp[0] = INF;
    dfs1(1, 0);
    dfs2(rt, 0);

    for(int i = 1; i <= n; i++) sum += 2 * d[i];
    cout << sum << '\n';

    anc[rt] = ++nn;
    for(int i = 1; i <= n; i++) pt[anc[i]].push(i);
    for(int i = 1; i <= nn; i++) {
        mn.push({i, pt[i].top()});
        sz.push({i, cs[i] = pt[i].size() * 2});
    }

    for(int i = 1; i <= n; i++) {
        int p1 = anc[i], p2, j;
        sz.erase({p1, cs[p1]}); 
        sz.push({p1, --cs[p1]}); 
        if(sz.top().sz == n - i + 1 && sz.top().id != nn) p2 = sz.top().id;
        else p2 = mn.top(p1).id;
        j = pt[p2].top();
        ans[i] = j;
        mn.erase({p2, j});
        sz.erase({p2, cs[p2]});
        pt[p2].pop();
        if(!pt[p2].empty()) mn.push({p2, pt[p2].top()});
        sz.push({p2, --cs[p2]});
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

AT_arc076_d [ARC076F] Exhausted?

有 \(m\) 个椅子在数轴上排列，第 \(i\) 张椅子的坐标为 \(i\)。

有 \(n\) 个人，第 \(i\) 个人希望坐在 \([1,l_i]\cup [r_i,m]\) 中的任意一把椅子上。问最多有多少个人不能坐在椅子上。

\(n,m\le 2\times 10^5\)

根据霍尔定理推广 \(1\)，我们只需求 \(|S|-|c(S)|\) 的最大值。

注意到 \(c(S)\) 也形如 \([1,l]\cup[r,m]\)。为了方便考虑和书写，将所有 \([1,l]\cup [r,m]\) 取补转化为区间，问题转化为求 \(|S|-\overline{\bigcap_{i\in S} [l_i+1,r_i-1]}=|S|-m+\bigcap_{i\in S} [l_i+1,r_i-1]\)。再分讨掉 \(\bigcap_{i\in S}[l_i+1,r_i-1]=\varnothing\) 的情况，此时 \(|S|-|c(S)|=n-m\)，注意特判。

接着考虑 \(\bigcap_{i\in S}[l_i+1,r_i-1]\ne\varnothing\) 的情况，即 \(\max\{l_i+1\}\le\min\{r_i-1\}\)。令 \(l_i\gets l_i+1,\ r_i\gets r_i-1\)，即求 \(\max\bigl\{|S|+\min\{r_i\}-\max\{l_i\}\big\}-m\)。我们枚举 \(\max\{l_i\}\)，即扫描 \(l_i\)，只考虑 \(l_i\le lim\) 的 \(i\)，用数据结构维护 \(\max\bigl\{|S|+\min\{r_i\}\big\}\) 即可。

时间复杂度 \(O(n\log n+n\log 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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;

struct myPair {
    int l, r;
    inline bool operator<(const myPair &b) const {
        return l < b.l;
    }
};

int n, m, ans;
myPair a[N];

namespace SegT {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        mx[p] = max(mx[lc(p)], mx[rc(p)]);
    }
    inline void move_tag(int p, int tg) {
        mx[p] += tg;
        tag[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
    void build(int p, int l, int r) {
        if(l == r) {
            mx[p] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mx[p];
        push_down(p);
        int mid = (l + r) >> 1;
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        return max(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;

    sort(a + 1, a + 1 + n);

    if(n > m) ans = n - m;

    ++m;
    SegT::build(1, 1, m);

    for(int i = 1; i <= n; i++) {
        SegT::add(1, 1, m, 1, a[i].r, 1);
        ans = max(ans, SegT::query(1, 1, m, a[i].l + 1, m) - a[i].l - m);
    }

    cout << ans << endl;

    return 0;
}

DAG 链覆盖 & Dilworth 定理

给定一个 DAG 的传递闭包，你需要选择一些点，且不存在两个点之间有连边，问最多选多少个点。

满足条件的点集 \(S\) 被称为反链，这个问题也被称为最长反链。

用若干条不重叠的路径覆盖 DAG 上的所有点，被称为 DAG 的链覆盖。

Dilworth 定理

DAG 传递闭包（偏序集）的最长反链等于最少链覆盖。

考虑如何求出 DAG 传递闭包的最小链覆盖。注意到问题可以转化为：选择一些边（组成链），每个节点的入度和出度均不超过 \(1\)，最多选择多少条边。最终答案等于 \(n\ -\) 选择的边数。

我们联想到最大匹配，最大匹配要求每个节点的度数不超过 \(1\)。因此我们可以将一个节点 \(u\) 拆分成两个节点 \(u_{in}\) 和 \(u_{out}\) 分别考虑。原图的一条边 \((u,v)\) 就对应新图上的 \((u_{out},v_{in})\)。跑最大匹配即可。

P3974 [TJOI2015] 组合数学

给定一个网格图，一些格子里有物品，一个格子内可能有多个物品。每次，你可以从网格图的左上角走到右下角，只能向右或向下走，每走到一个格子至多带走一个物品。问至少需要走几次才能捡到所有物品。

\(n, m\le 1000,\ a_i\le 10^6\)

注意到严格偏序可以转化为非严格偏序，因此 Dilworth 定理仍然成立，我们只需求出原图的最长反链（带权）即可。我们从左下向右上 dp，用 \(f_{i,j}\) 表示从左下到 \((i,j)\) 的最长反链长度。转移就是 \(f_{i,j}=\max(f_{i+1,j},f_{i,j-1},f_{i-1,j-1}+a_{i,j})\)，\(f_{1,m}\) 即是答案。时间复杂度 \(O(nm)\)。

代码 
 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<iostream>
#define int long long
using namespace std;
const int N = 1010;

int T;
int n, m;

int a[N][N];
int f[N][N];

signed main() {

    cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        int ans = 0;
        for(int i = n; i >= 1; i--) {
            for(int j = 1; j <= m; j++) {
                f[i][j] = max(max(f[i + 1][j], f[i][j - 1]), f[i + 1][j - 1] + a[i][j]);
                ans = max(ans, f[i][j]);
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Y12-3 出租车订单

在一个 \(200\times 200\) 的平面网格图上有 \(m\) 个人，每个人有一个初始坐标 \((a,b)\) 和目的地 \((c,d)\)，以及出发时间 \(t\)。

有若干出租车，出租车从一个点移动到另一个点的耗时等于两个点之间的曼哈顿距离。你需要用出租车将每个人都运送到目的地。每辆出租车的初始位置是任意的。出租车运送完一个人之后，可以前往另一个人的位置，并等待这个人出发。任意时刻一辆出租车只能运载一个人。问按时接送这些人，最少需要多少出租车。

\(m\le 500\)

注意到人数很小，因此我们可以预处理一些信息，简化问题。我们可以枚举两个人 \(i,j\)，然后判断送完 \(i\) 之后能不能去送 \(j\)。

这样，我们就建出了一张严格偏序 DAG，问题转化为 DAG 路径覆盖问题，使用最大匹配求解即可。

代码 
 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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;

int T, n, ans;

struct Edge {
    int v, next;
} pool[N * N];
int ne, head[2 * N];

void addEdge(int u, int v) {
    pool[++ne] = {v + N, head[u]};
    head[u] = ne;
}

int abs(int x) {
    if(x < 0) return -x;
    return x;
}

struct Pt {
    int x, y;
    inline int operator-(const Pt &b) const {
        return abs(x - b.x) + abs(y - b.y);
    }
};

struct sb {
    Pt s, t;
    int tm;
} a[N];

bool check(const sb &a, const sb& b) {
    return (b.tm - 1 - a.tm) >= (b.s - a.t) + (a.t - a.s);
}

int vis[2 * N], link[2 * N];
bool dfs(int u) {
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        if(!link[v] || dfs(link[v])) {
            link[v] = u;
            return true;
        }
    }
    return false;
}

int main() {

    cin >> T;
    while(T--) {
        ne = 0;
        memset(head, 0, sizeof(head));
        memset(link, 0, sizeof(link));
        cin >> n;
        for(int i = 1; i <= n; i++) {
            int h, m;
            cin >> h;
            getchar();
            cin >> m;
            a[i].tm = h * 60 + m;
            cin >> a[i].s.x >> a[i].s.y >> a[i].t.x >> a[i].t.y;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(check(a[i], a[j])) addEdge(i, j);
            }
        }
        ans = n;
        for(int i = 1; i <= n; i++) {
            for(int j = N; j <= N + n; j++) vis[j] = 0;
            ans -= dfs(i);
        }
        cout << ans << endl;
    }

    return 0;
}

P4298 [CTSC2008] 祭祀

给定一个偏序集，请你输出它的最长反链长度，并构造一组反链，同时判断每个点是否可能在最长反链中。

\(n\le 100\)

第一问显然。

对于第二问，先建出二分图跑出最大匹配，考虑如何构造解。这里给出结论：

  • 从二分图左侧的非匹配点开始遍历交错树；
  • 左侧没被遍历到的点 + 右侧被遍历到的点 = 最小点覆盖；

我们现在尝试说明这种方式确实能得到最小点覆盖。

先证选出的节点数量等于最大匹配。首先注意到左侧的非匹配点一定都被遍历到了，不会被选择，因此选出的点只可能是匹配点；右侧被遍历到的点也一定是匹配点（从左侧的非匹配点沿交错树不可能到达右侧的非匹配点，否则是增广路）。同时一条匹配边两侧是否被遍历的状态是一致的，因此一条匹配边有且仅有一个端点被选中。

再证选出的节点可以覆盖所有边。对于匹配边，上面已经说明了；对于非匹配边，更不可能出现左侧访问而右侧没有访问的情况。证毕。

对于第三问，我们依次枚举每个点，钦定该点被选，然后再跑最大匹配，判断是否还能得到原先的最大匹配。钦定选择的过程就是删掉该点和所有与该点有偏序关系的点。

时间复杂度 \(O(n^4)\)，稠密图跑得飞快，瓶颈在第 \(3\) 问。

代码 
  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
#include<iostream>
#include<cassert>
using namespace std;
const int N = 110;

int n, m;
int k; // 链覆盖数量

int to[N][N];

int ban[N];
int link[2][N];
int vis1[N], tm;

void clear() {
    for(int i = 1; i <= n; i++) ban[i] = link[0][i] = link[1][i] = 0;
}

bool dfs1(int u) {
    if(ban[u]) return false;
    for(int v = 1; v <= n; v++) {
        if(!to[u][v] || vis1[v] == tm) continue;
        if(ban[v]) continue;
        vis1[v] = tm;
        if(!link[1][v] || dfs1(link[1][v])) {
            link[1][v] = u;
            link[0][u] = v;
            return true;
        }
    }
    return false;
}

bool vis2[2][N];

void dfs2(int u) {
    vis2[0][u] = 1;
    for(int v = 1; v <= n; v++) {
        if(!to[u][v] || v == link[0][u]) continue;
        if(vis2[1][v]) continue;
        vis2[1][v] = 1;
        if(link[1][v]) dfs2(link[1][v]);
    }
}

bool check(int u) {
    clear();
    int res = n;
    ban[u] = 1;
    --res;
    for(int v = 1; v <= n; v++) {
        if(v != u && (to[u][v] || to[v][u])) ban[v] = 1, --res;
    }
    for(int i = 1; i <= n; i++) {
        ++tm;
        res -= dfs1(i);
    }
    return res == k - 1;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        to[u][v] = 1;
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                to[i][j] = to[i][j] || (to[i][k] && to[k][j]);
            }
        }
    }

    k = n;
    for(int i = 1; i <= n; i++) {
        ++tm;
        k -= dfs1(i);
    }
    cout << k << '\n';

    for(int i = 1; i <= n; i++) {
        if(link[0][i]) continue;
        dfs2(i);
    }
    for(int i = 1; i <= n; i++) {
        if(vis2[0][i] && !vis2[1][i]) cout << '1';
        else cout << '0';
    }
    cout << '\n';

    for(int i = 1; i <= n; i++) {
        if(check(i)) cout << '1';
        else cout << '0';
    }
    cout << '\n';

    return 0;
}