二分图匹配

二分图匹配

二分图匹配是个经典问题——两组节点在图上尽可能的匹配。

匈牙利算法以不断寻找增光路的方式,寻找更多的匹配;

思想如下:

  1. 从未匹配的点c开始寻找链接的点v,如果v也是未匹配,则匹配成功。如果该点已经匹配了u,则递归尝试让u匹配其他节点。
  2. 如果v匹配失败,那就找找c的其他点。

题解参考

模板写法

const int N=605;
const int n=105;
vector<int> g[N];
int from[N], tot=0;
bool use[N];

bool match(int x){
    for(int i=0; i<g[x].size(); ++i)
    if(!use[g[x][i]]){
        use[g[x][i]]=true;
        if(from[g[x][i]]==-1 || match(from[g[x][i]])){
            from[g[x][i]]=x;
            return true;
        }
    }
    return false;
}

int hungary(){
    tot=0;
    memset(from, -1, sizeof from);
    for(int i=1; i<=n; ++i){
        memset(use, 0x00, sizeof use);
        if(from[i] != -1 && match(i)) ++tot;
    }
    return tot;
}

二分图染色问题

785. 判断二分图

思路:

炫酷的lambda写法~

代码:

class Solution {
public:
    int flag = 0;
    vector<int> color;

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        int colors[n];
        memset(colors, -1, sizeof colors);

        function<bool(int, int)> dfs = [&](int node, int color) -> bool {
            colors[node] = color;
            for(auto c : graph[node]){
                if(colors[c] == -1 && !dfs(c, 1 - color)) return false;
                if(colors[c] == color) return false;
            }
            return true;
        };
        for(int i = 0; i < n; ++i)
            if(colors[i] == -1 && !dfs(i, 1)) return false;
        return true;
    }


};

棋盘覆盖

思路:

棋盘就是个抽象的图。

二分图思路做下来就行。

代码:

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int N = 105;
using PII = pair<int,int>;
int n, m;
bool maze[N][N];
PII match[N][N]; // 直接存储匹配量,比较方便~
bool vis[N][N];

int dx[] = {-1, 0, 0, 1}; //1 与 4 对应
int dy[] = {0, 1, -1, 0}; // 2与3 对应

bool find(int x, int y){
    // vis[x][y] = 1;
    for(int i = 0 ;i < 4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx && nx <= n && ny && ny <= n && !maze[nx][ny] && !vis[nx][ny]){ // 访问有效的,不在该次扩展中访问过的节点
            vis[nx][ny] = 1; // 该节点已经访问
            auto t1 = match[nx][ny].first;
            auto t2 = match[nx][ny].second;
            if(t1 == -1 || find(t1, t2)){ // 如果该节点未匹配或者该节点的匹配被更新了
                match[x][y] = {nx, ny};
                match[nx][ny] = {x, y};
                return true;
            }
        }

    }
    return false;
}

int main(){
    int a, b;
    scanf("%d%d", &n, &m);
    while(m--){
        scanf("%d%d", &a, &b);
        maze[a][b] = 1;        
    }
    memset(match, -1, sizeof match);
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
//            if((i+j)&0x01 && !maze[i][j]){  // 为什么不排除已匹配成功的节点
            if(match[i][j].first != -1 && !maze[i][j]){  // 为什么不排除已匹配成功的节点
                memset(vis, 0x00, sizeof vis);
                if(find(i, j)) cnt++;
            }
        }
    }
    printf("%d", cnt);

    return 0;
}   

Comments