跳转至

二分图

对于图 \(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 n)\)。

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)\)，在随机稠密图上跑的飞快（因为增广路很短，比 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
#include "testlib.h"
using namespace std;

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

int main() {

    cout << n << ' ' << m << '\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;
}

DAG 链覆盖 & Dilworth 定理

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

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

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

Dilworth 定理

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

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

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

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\)

第一问显然。

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

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

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

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

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

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

代码 
  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;
}