Loading... # 问题 [LeetCode LCP 04](https://leetcode-cn.com/problems/broken-board-dominoes/) 该题看上去与二分图匹配无关，但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格，而这两格必须是相邻的。因此如果把相邻的两格看成分别属于X、Y两个集合的节点，相邻的节点之间认为有一条（黑色）边相连，放骨牌看做将被覆盖的两格之间的边染成红色；由于一格（一个节点）只能被一个骨牌覆盖（被一条红边连接），那么连接的方式整个就是二分图的一个匹配。如何构建这张图呢？由于相邻的点属于不同的集合，因此仿照国际象棋的棋盘“间隔地”染色就好了。于是，相邻格子之间对应的边连接的都是属于不同集合的节点，相同集合的节点因为对应的不是相邻格子都不直接相连，形成了二分图。最后，能放置骨牌的最大数量就是二分图最大匹配中的边数。 二分图最大匹配可以用匈牙利算法解决，也可以转化成最大流解决，本次使用前者。匈牙利算法的核心操作其实与后者还挺像，后者是寻找增流路径，而前者是寻找一个“交互道路”（节点颜色交替的道路），其实都可以理解为增广道路（augmentation path）。只不过，由于在二分图匹配中一条边要么就是选要么就是不选，相当于是特殊的“流”，0或者1，因此最大流的“退流”操作，被简化为了异或操作。无论是从算法中具体的寻找增广道路去想，还是在宏观上进行问题的转化，本质上，二分图最大匹配就是最大流的特殊情况。 # 实现 本题首先需要建图。建图中，格子的坐标(i, j)（一个数对）需要被转化成点的序号（一个值），这里可以采用二维数组的索引方式。相邻格子染成不同颜色，可以用(i + j)的奇偶性来判断。其它的就很简单了。 建图之后直接调用匈牙利算法是可以的。不过为了加快一点速度，可以提供一个初始匹配。下面的代码在建图过程中简单地“铺上了横向的多米诺骨牌”作为初始匹配。 匈牙利算法中，寻找交互道路的过程用DFS实现。说白了，这一步就是从X集合中未搜索过的点出发，走一条在X、Y之间反复横跳的道路，最后以属于Y集合中而没有被匹配的点作为终点停止。 最终实现的算法类Hungarian接受三个参数初始化，分别是二分图的邻接表表示（因为该算法中常用到邻点，因此邻接表比邻接矩阵省时），每个点属于哪个集合，以及初始匹配是什么。构造函数中已调用核心算法，可以直接构造后调用getAns获取最大匹配数。 ```cpp class Hungarian { vector< vector<int> >& graph; // adjacency list vector<bool>& type; // X: 0; Y: 1 vector<int>& match; // not matched: -1 int n; int end; int total; void dfs(const int now, vector<bool>& visited, stack<int>& path) { if (type[now] == 1) { if (match[now] == -1) end = now; // return; else // if (match[now] != -1) { // now -> match[now] path.emplace(match[now]); dfs(match[now], visited, path); if (end != -1) return; path.pop(); } } else // if (type[now] == 0) { for (auto& iter : graph[now]) { // now -> iter in Y if (visited[iter] == false) { visited[iter] = true; path.emplace(iter); dfs(iter, visited, path); if (end != -1) break; path.pop(); visited[iter] = false; } } // break here // return; } } void work() { queue<int> not_searched; for (int i = 0; i < n; i++) { if (type[i] == 0 && graph[i].size()) { if (match[i] == -1) not_searched.emplace(i); else total++; } } while (not_searched.size()) { int start = not_searched.front(); not_searched.pop(); vector<bool> visited(n, false); stack<int> path; end = -1; path.emplace(start); dfs(start, visited, path); if (end != -1) // find an augmenting path { // start -> ... -> end total++; while (path.size()) { int tmp = path.top(); path.pop(); match[tmp] = path.top(); match[path.top()] = tmp; path.pop(); } } } } public: Hungarian(vector< vector<int> >& _g, vector<bool>& _t, vector<int>& _m): graph(_g), type(_t), match(_m), n(_g.size()), total(0) { work(); } int getAns() { return total; } }; class Solution { int N; int M; int points; bool in_graph(const int x, const int y) { return 0 <= x && x < N && 0 <= y && y < M; } int get_index(const int x, const int y) { return x * M + y; } bool get_type(const int x, const int y) { return (x + y) % 2; } public: int domino(int n, int m, vector<vector<int>>& broken) { N = n; M = m; points = n * m; bool _broken[8][8] = { 0 }; vector< vector<int> > graph(points); // adjacency list vector<bool> type(points, 0); // X: 0; Y: 1 vector<int> match(points, -1); // not matched: -1 for (auto& iter : broken) { _broken[iter[0]][iter[1]] = 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!_broken[i][j]) { int now = get_index(i, j); type[now] = get_type(i, j); if (in_graph(i - 1, j) && !_broken[i - 1][j]) { // up graph[now].push_back(get_index(i - 1, j)); } if (in_graph(i + 1, j) && !_broken[i + 1][j]) { // down graph[now].push_back(get_index(i + 1, j)); } if (in_graph(i, j - 1) && !_broken[i][j - 1]) { // left graph[now].push_back(get_index(i, j - 1)); } if (in_graph(i, j + 1) && !_broken[i][j + 1]) { // right int right = get_index(i, j + 1); graph[now].push_back(right); if (type[now] == 0) { match[now] = right; match[right] = now; } } } } } // for in i return Hungarian(graph, type, match).getAns(); } }; ``` Last modification：June 29th, 2020 at 05:27 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author