问题

LeetCode LCP 04

该题看上去与二分图匹配无关,但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格,而这两格必须是相邻的。因此如果把相邻的两格看成分别属于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();
    }
};
Last modification:June 29th, 2020 at 05:27 pm
如果觉得我的文章对你有用,请随意赞赏