xxyQwQ
0%

【题解】ACMOJ 1572 二分图

发表于 分类于

题目描述

ACMOJ - 1572 - 填满棋盘

在 $n$ 行 $m$ 列的棋盘上，挖去 $k$ 个格子，用若干 $1\times 2$ 的棋子不可重叠地放置在剩余格子中，问是否可以铺满剩余棋盘

共有 $T$ 组测试数据（$T\leq 3$），每组数据保证 $n,m\leq 32$，$k<n\times m$

问题分析

数据范围很小，即使 $O(n^2m^2)$ 的算法也可以轻松解决

题目以棋盘为背景，因此很容易想到国际象棋棋盘的黑白交错。我们以相同的方式给棋盘染色，则放置的棋子有如下性质：

  • 棋子必然位于一对相邻的黑白格上
  • 只要存在一对相邻的黑白格，必然可以放置一枚棋子

我们不妨将每个格子视为一个节点，从每个黑色格子出发，向与其相邻的每个白色格子连边，这样便形成了一张二分图。该二分图完美建模了棋子放置的情况，一对匹配恰好代表一枚棋子被放置，二分图的最大匹配恰好代表放置棋子的最大数目，故有结论：

  • 棋子可以铺满剩余棋盘的充要条件是：对应二分图的最大匹配等于剩余格数的一半

在此二分图上跑匈牙利算法，即有 $O(n^2m^2)$ 的复杂度，但是也可以考虑复杂度更加优秀的网络流方法

我们以如下方式构造网络图：

  • 从超级源点出发，向每个黑色格子连一条容量为 $1$ 的边
  • 从每个白色格子出发，向超级汇点连一条容量为 $1$ 的边
  • 从每个黑色格子出发，向与其相邻的每个白色格子连一条容量为 $1$ 的边

在此网络图上采用 Dinic 算法跑最大流，即为二分图的最大匹配，由于约有 $nm$ 个节点和 $2nm$ 条边，时间复杂度为 $O(m^{\frac{3}{2}}n^{\frac{3}{2}})$（实际上根本跑不满）

一些细节

  1. 由于存在多组测试数据，每次要清空head数组和broken数组，并重置原点和汇点的标号
  2. 每次total要重置且初始值为 $1$（老生常谈）
  3. 数组大小至少为 $32\times 32+2=1026$，我起初开到 $1025$ 发生了一些不可预知的 TLE（悲）

代码

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
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <cstring>
#include <queue>
#include <algorithm>
const int NMAX = 1035, INF = 0x3f3f3f3f;
const int dx[5] = {-1, 0, 1, 0}, dy[5] = {0, -1, 0, 1};

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

template <typename T, typename... Ts>
void read(T &value, Ts &...remain)
{
    read(value);
    read(remain...);
}

struct Edge
{
    int t, w, n;
    Edge(int _t = 0, int _w = 0, int _n = 0) : t(_t), w(_w), n(_n) {}
} edge[NMAX << 3];
int head[NMAX], start[NMAX], depth[NMAX], T, n, m, k, s, t, total;
bool broken[35][35];

inline void insert(int u, int v, int w)
{
    edge[++total] = Edge(v, w, head[u]);
    head[u] = total;
}

bool bfs()
{
    memset(depth, 0, sizeof(depth)), memcpy(start, head, sizeof(head));
    std::queue<int> q;
    q.push(s), depth[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].n)
        {
            int v = edge[i].t;
            if (edge[i].w && !depth[v])
                depth[v] = depth[u] + 1, q.push(v);
        }
    }
    return depth[t];
}

int dfs(int u, int a)
{
    if (u == t || !a)
        return a;
    int f, r = 0;
    for (int &i = start[u]; i; i = edge[i].n)
    {
        int v = edge[i].t;
        if (edge[i].w && depth[v] == depth[u] + 1 && (f = dfs(v, std::min(a, edge[i].w))))
        {
            r += f, a -= f;
            edge[i].w -= f, edge[i ^ 1].w += f;
            if (!a)
                break;
        }
    }
    return r;
}

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

void construct()
{
    memset(head, 0, sizeof(head)), memset(broken, 0, sizeof(broken));
    read(n, m, k), s = 0, t = n * m + 1, total = 1;
    for (int i = 1, x, y; i <= k; i++)
        read(x, y), broken[x][y] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (broken[i][j])
                continue;
            int p = (i - 1) * m + j;
            if ((i + j) & 1)
                insert(p, t, 1), insert(t, p, 0);
            else
            {
                insert(s, p, 1), insert(p, s, 0);
                for (int _k = 0; _k < 4; _k++)
                {
                    int _i = i + dx[_k], _j = j + dy[_k];
                    if (_i < 1 || _i > n || _j < 1 || _j > m || broken[_i][_j])
                        continue;
                    int _p = (_i - 1) * m + _j;
                    insert(p, _p, 1), insert(_p, p, 0);
                }
            }
        }
}

int main()
{
    read(T);
    while (T--)
    {
        construct();
        int flow = dinic();
        printf("%s\n", (2 * flow == n * m - k) ? "YES" : "NO");
    }
    return 0;
}