二分图和匈牙利算法

leetcode题目链接

二分图,即对于一个图$g=(V,E)$,将节点分成两个集合,使得$\forall e\in E$,它的两端点分别位于两个集合$A,B$中

对于二分图,有一些概念

  • 匹配:顶点$i$和$j$的边$e_{ij}$,并且将$i$放入$A$,$j$放入$B$
  • 非匹配边:顶点$i$和$j$的边不用来匹配
  • 增广路:匹配边和非匹配边交替出现的情况

匈牙利算法:

  1. 将一条边作为匹配边,并且匹配边的两个端点作为非匹配边
  2. 交换匹配边和非匹配边,那么当前路径就会多一条匹配边
  3. 重复2,直到没有新的匹配边加入

代码实现

class Solution {
public:
    void constr_graph(int n,int m,vector<vector<int>> &broken,vector<vector<int>> &r){
        vector<vector<int>> occupy(n,vector<int>(m));
        for(auto b:broken){
            occupy[b[0]][b[1]]=1;
        }
        // cout<<"=====occupy====="<<endl;
        // for(int i=0;i<n;i++){
        //     cout<<i<<":";
        //     for(auto n:occupy[i]){
        //         cout<<n<<",";
        //     }
        //     cout<<endl;
        // }
        // cout<<"================"<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 首先把点分成两组,即奇数只能在pb,偶数只能在pa
                if(i+j&1)continue;
                if(occupy[i][j]!=0)continue;
                int st=i*m+j;
                if(i>0&&occupy[i-1][j]==0){
                    r[st].push_back((i-1)*m+j);
                }
                if(i<n-1&&occupy[i+1][j]==0){
                    r[st].push_back((i+1)*m+j);
                }
                if(j>0&&occupy[i][j-1]==0){
                    r[st].push_back(i*m+j-1);
                }
                if(j<m-1&&occupy[i][j+1]==0){
                    r[st].push_back(i*m+j+1);
                }
            }
        }
    }
    int dfs(vector<vector<int>>&g,int st,vector<int> &vi,int dfn,vector<int>&pa,vector<int>&pb){
        int m1=0,m2;
        vi[st]=dfn;
        for(auto i:g[st]){
            if(pb[i]==-1){ // 如果另一个节点还没有连接任何边
                pa[st]=i;
                pb[i]=st;
                return true;
            }
        }
        // 如果所有节点都连接边了,表明自身是一个孤立的点,应该请求自身相连的点换边
        for(auto i:g[st]){
            // 当前路径深度优先换边
            // 另一个节点没有到达这个深度,则给上一个连接的点更换连接对象尝试
            if(vi[pb[i]]!=dfn&&dfs(g,pb[i],vi,dfn,pa,pb)){
                pa[st]=i;
                pb[i]=st;
                return true;
            }
        }
        return false;
    }

    int solve(vector<vector<int>> &g){
        int mn=g.size(),dfn=0,r=0;
        // cout<<"=====graph====="<<endl;
        // for(int i=0;i<mn;i++){
        //     cout<<i<<":";
        //     for(auto n:g[i]){
        //         cout<<n<<",";
        //     }
        //     cout<<endl;
        // }
        // cout<<"================"<<endl;
        vector<int> vis(mn),pa(mn,-1),pb(mn,-1);
        while(true){
            dfn++;
            int cnt=0;
            // 以3x3为例
            // 第一轮循环:0->1,2->5,4->3,6->7,cnt=4
            // 第二轮循环:没有,因为发现所有连接点都无法换边
            for(int i=0;i<mn;i++){
                // 本身没有加入集合并且成功匹配
                if(pa[i]==-1&&dfs(g,i,vis,dfn,pa,pb)){
                    cnt++;
                }
            }
            if(cnt==0)break;
            r+=cnt;
        }
        return r;
    }
    int domino(int n, int m, vector<vector<int>>& broken) {
        vector<vector<int>> g(m*n);
        constr_graph(n,m,broken,g);
        return solve(g);
    }
};

参考

简单理解增广路与匈牙利算法 - 朴楞蛾子的文章 - 知乎 https://zhuanlan.zhihu.com/p/208596378

https://leetcode.cn/problems/broken-board-dominoes/solutions/983247/suan-fa-xiao-ai-cong-ling-dao-yi-jiao-hu-8b4k/