问题
该题看上去与二分图匹配无关,但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格,而这两格必须是相邻的。因此如果把相邻的两格看成分别属于X、Y两个集合的节点,相邻的节点之间认为有一条(黑色)边相连,放骨牌看做将被覆盖的两格之间的边染成红色;由于一格(一个节点)只能被一个骨牌覆盖(被一条红边连接),那么连接的方式整个就是二分图的一个匹配。如何构建这张图呢?由于相邻的点属于不同的集合,因此仿照国际象棋的棋盘“间隔地”染色就好了。于是,相邻格子之间对应的边连接的都是属于不同集合的节点,相同集合的节点因为对应的不是相邻格子都不直接相连,形成了二分图。最后,能放置骨牌的最大数量就是二分图最大匹配中的边数。
二分图最大匹配可以用匈牙利算法解决,也可以转化成最大流解决,本次使用前者。匈牙利算法的核心操作其实与后者还挺像,后者是寻找增流路径,而前者是寻找一个“交互道路”(节点颜色交替的道路),其实都可以理解为增广道路(augmentation path)。只不过,由于在二分图匹配中一条边要么就是选要么就是不选,相当于是特殊的“流”,0或者1,因此最大流的“退流”操作,被简化为了异或操作。无论是从算法中具体的寻找增广道路去想,还是在宏观上进行问题的转化,本质上,二分图最大匹配就是最大流的特殊情况。
实现
本题首先需要建图。建图中,格子的坐标(i, j)(一个数对)需要被转化成点的序号(一个值),这里可以采用二维数组的索引方式。相邻格子染成不同颜色,可以用(i + j)的奇偶性来判断。其它的就很简单了。
建图之后直接调用匈牙利算法是可以的。不过为了加快一点速度,可以提供一个初始匹配。下面的代码在建图过程中简单地“铺上了横向的多米诺骨牌”作为初始匹配。
匈牙利算法中,寻找交互道路的过程用DFS实现。说白了,这一步就是从X集合中未搜索过的点出发,走一条在X、Y之间反复横跳的道路,最后以属于Y集合中而没有被匹配的点作为终点停止。
最终实现的算法类Hungarian接受三个参数初始化,分别是二分图的邻接表表示(因为该算法中常用到邻点,因此邻接表比邻接矩阵省时),每个点属于哪个集合,以及初始匹配是什么。构造函数中已调用核心算法,可以直接构造后调用getAns获取最大匹配数。
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();
}
};