二分匹配核心算法:匈牙利算法(最大流的写法后续更新)

注意:匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值

先上匈牙利算法基础模板(求最大匹配数)

bool lj[MAXN][MAXN], vis[MAXN];
int link[MAXN];
int n;

bool find(int x) {  //算法核心,深搜操作
    for(int i=0; i<n; ++i) {
        if(lj[x][i]&&!vis[i]) {
            vis[i]=1;
            if(link[i]==-1||find(link[i])) {  //这个点没有关联或者它的关联点能找到别的关联
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int k;
    cin>>n>>k;
    for(int i=0; i<k; i++) {
        int x, y;
        cin>>x>>y;
        lj[x][y]=1;
    }
    //以下正式开始匈牙利算法
    int cnt=0;
    memset(link,-1,sizeof(link));
    for(int i=0; i<n; ++i) {
        memset(vis,0,sizeof(vis));
        if(find(i)) cnt++;
    }
    
    return 0;
}

二分匹配知识点

  1. 最大匹配数=最小点覆盖
  2. 最小路径覆盖=最大独立集
  3. 最大匹配数+最大独立集=V

常见模型

  1. 在二维平面上将坐标按X,Y当做两个分图, 而坐标则看作分图之间的边;
  2. 有时需要重建X,Y的定义,如HDOJ 1045
  3. 其他类型动动脑子就好。