二分图匹配（匈牙利算法）

博主： Osilly
发布时间：2021 年 04 月 19 日
1959次浏览
2 条评论
1494字数
分类：图论

1.什么是二分图？

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
简单来说，就是一个可以分割成两个顶点集的图（可以类比男生女生，男生与女生彼此之间可以有恋爱但是男生和男生以及女生和女生之间不能有关系）
~~百合和基友爬嗷~~

2.我们二分图一般需要我们处理什么样的问题？

我们继续拿男生和女生配对作为例子
我们有时候一个男生会对多个女生有好感，同样一个女生也有可能对多个男生有好感，他们之间就形成了一个二分图。
这时候需要求解：当一个男生只能和一个女生配对时，我们该如何配对才能使配对的数量最多？
这时候我们就需要二分图最大匹配算法

3.二分图最大匹配算法

现在主要求解二分图最大匹配有两种算法：匈牙利算法和dinic算法
时间复杂度分别为O（nm）和O（nm^0.5）
由于dinic算法是基于网络流的一个特殊情况，本文主要介绍匈牙利算法

4.匈牙利算法

关于匈牙利算法的解析，这篇博客学习起来会有很大的帮助
一个超棒的匈牙利算法解析
本文对算法一些细节部分进行解释
首先，上代码

int dfs(int x) {
  for (int i = 1; i <= m; i++) {
    if (line[x][i] == 1 && used[i] == 0) {
      used[i] = 1;
      if (match[i] == 0 || dfs(match[i])) {
        match[i] = x;
        return 1;
      }
    }
  }
  return 0;
}

for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }

这两部分便是代码的核心
匈牙利算法核心就是尽可能寻找新的增广路
这里借助下上面博客的图

算法的运行过程

我们如果要最大的配对数，按照算法的运行

第一步

for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }

我们选取1号男生为搜索配对对象进入dfs
这时，我们在dfs中查询女生与1号男生是否有好感（邻接矩阵），如果有好感并且这个女生之前没有被选择过，就将他们配对
并且，我们用match数组将女生的配对对象记录下来

这个match数组非常重要，不仅仅是记录女生的配对对象，同样标记女生有没有被匹配过，最为重要的，它作为之后算法回溯的指引

这里显然可以看出选择1号女生
同理，第二次循环查询2号男生时，同样找到了2号女生

第二步

这是现在的情况，我们进入第三次循环，找3号男生的配对
我们发现，3号男生第一个有好感的女生是1号女生，但是，1号女生已经被配对了
这时候，按照匈牙利算法，我们并不是直接放弃，而是看一看能不能通过挪动关系来保证1号男生换个配对
然后我们通过1号女生match数组回溯到1号男生，1号男生来选择下别的女生

used的数组的作用就在这里体现，来记录本次dfs中女生是否被查询过，查询过就不再重复查询

1号男生查询到了2号女生，很可惜，二号女生也被2号男生配对过了，但我们仍然不放弃，继续重复看一看二号男生可不可以找个新的配对

第三步

这时候，我们是现在这个情况
（黄色边表示待定）

我们的2号男生发现了3号女生，而且3号女生没有被配对过
nice！我们可以把3号女生和2号男生配对，然后回溯到2号女生，2号女生和1号男生配对，最后回溯到1号女生，1号女生和3号男生配对
现在我们从2对增加到了3对

第四步

现在还剩下4号男生，我们重复上面的操作，但是很可惜，无论怎么挪动配对，我们都无法做到在不减少配对数量的同时给4号男生增加一个对象
这时候4个男生查询结束，最后得到的最大匹配数为3

算法的核心

上面就是算法的详细运行情况，算法的核心就是，我们在不减少原先配对的数量的同时（可以改变关系但不减少数量），增加一个新的配对

二分图的一些例题

第一个自然是模板题
洛谷的P3386 【模板】二分图最大匹配

https://www.luogu.com.cn/problem/P3386

贴出代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 5e2 + 10;

int n, m, e;
int line[maxn][maxn];
int used[maxn];
int U[maxn];
int u, v;
int ans;

int dfs(int x) {
  for (int i = 1; i <= m; i++) {
    if (line[x][i] == 1 && used[i] == 0) {
      used[i] = 1;
      if (U[i] == 0 || dfs(U[i])) {
        U[i] = x;
        return 1;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m >> e;
  for (int i = 1; i <= e; i++) {
    cin >> u >> v;
    line[u][v] = 1;
  }
  for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }
  cout << ans;
  return 0;
}

第二个是洛谷的P2423 [HEOI2012]朋友圈
这是一个有点难度的二分图题目，做的时候真的很大提升了我对二分图配对的运用，而且要运用到一个小技巧——时间戳优化匈牙算法，看他人题解应该是要两个时间戳，代码只打了一个，最后两个样例卡了时间，完全正解移步洛谷题解区
解析待更

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 8e3 + 10;

int T;
int match[maxn], used[maxn];
int line[maxn][maxn];
int e[maxn][maxn];
int v[maxn], u[maxn];
int k1, k2;
int a, b, m;
int ans;
vector<int> vec1, vec2;  // 1 prime

int check(int x) {
  int re = 0;
  while (x) {
    if (x & 1) re++;
    x /= 2;
  }
  if (re % 2 == 0)
    return 1;
  else
    return 0;
}

void init() {
  for (int i = 1; i <= b; i++) {
    for (int j = 1; j <= b; j++) {
      if (v[i] % 2 == 1 && v[j] % 2 == 0 && check(v[i] | v[j])) {  
        e[i][j] = 1;
      }
    }
  }
}

int dfs(int x) {
  for (int i = 0; i < vec2.size(); i++) {
    if (e[vec1[x]][vec2[i]] == 1 && used[vec2[i]] != k1) {
      used[vec2[i]] = k1;
      if (match[vec2[i]] == 0 || dfs(match[vec2[i]])) {
        match[vec2[i]] = vec1[x];
        return 1;
      }
    }
  }
  return 0;
}

void add1(int x, int y) {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    int re = 0;
    if (line[x][i] == 1) re++;
    if (line[y][i] == 1) re++;
    if (re == 2) {
      if (v[i] % 2 == 1)
        vec1.push_back(i);
      else
        vec2.push_back(i);
    }
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum + 2);
}

void add2(int x) {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    if (line[x][i] == 1) {
      if (v[i] % 2 == 1)
        vec1.push_back(i);
      else
        vec2.push_back(i);
    }
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum + 1);
}

void add3() {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    if (v[i] % 2 == 1)
      vec1.push_back(i);
    else
      vec2.push_back(i);
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum);
}

int main() {
  cin >> T;
  while (T--) {
    vec1.clear();
    vec2.clear();
    ans = 0;
    k1 = 0;
    memset(used, 0, sizeof(used));
    cin >> a >> b >> m;
    for (int i = 1; i <= a; i++) cin >> u[i];
    for (int i = 1; i <= b; i++) cin >> v[i];
    for (int i = 1; i <= m; i++) {
      int x, y;
      cin >> x >> y;
      line[x][y] = 1;
    }
    // k2 = 2;//代表无关系
    init();
    for (int i = 1; i <= a; i++) {
      for (int j = i+1; j <= a; j++) {
        if ((u[i] % 2) != (u[j] % 2)) add1(i, j);
      }
    }
    for (int i = 1; i <= a; i++) {
      add2(i);
    }
    add3();
    cout << ans << endl;
  }
  return 0;
}

第三题牛客的Graph Coloring I

https://ac.nowcoder.com/acm/problem/19790

一道经典的二分图判断题，这道题的难点和创新处在于奇数环的路径还原

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;

vector<int> vec[maxn];
int n, m;
int u, v;
int pre[maxn];
int color[maxn];
int flag = 0;
int k;
int used[maxn];

int dfs(int s, int c) {
  color[s] = c;
  for (int i = 0; i < vec[s].size(); i++) {
    if (color[vec[s][i]] == c) {
      pre[vec[s][i]] = s;
      k = s;
      return 0;
    }
    if (color[vec[s][i]] == 0 && !dfs(vec[s][i], -c)) {
      if (!pre[vec[s][i]]) pre[vec[s][i]] = s;
      return 0;
    }
  }
  return 1;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  if (dfs(1, 1)) {
    cout << '0' << endl;
    for (int i = 1; i <= n; i++) {
      if (color[i] == 1)
        cout << 0 << ' ';
      else
        cout << 1 << ' ';
    }
  } else {
    int sum = 0;
    int v = k;
    while (pre[v] != k) {
      v = pre[v];
      sum++;
    }
    cout << sum + 1 << endl;
    v = k;
    while (pre[v] != k) {
      cout << v << ' ';
      v = pre[v];
    }
    cout << v;
  }
  return 0;
}

最后修改：2021 年 04 月 27 日 05 : 29 PM

2 条评论

吴
April 23rd, 2021 at 10:34 pm

三百加油，爸爸永远爱你

回复
美女
April 19th, 2021 at 10:57 pm

好耶

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rantrism
您好～我是腾讯云+社区的运营，关注了您分享的技术文章，觉得内容...
防水材料加盟
感谢分享赞一个
风子
名称：君名IU简介：学习ing图标：http://www.th...
安心
大佬为啥上传不了，按照上面步骤后
edisoncgh
轩轩更新了！|´・ω・)ノ

7-1 初识Redis
浏览次数: 837
2-5 java 和 MongoDB
浏览次数: 797
DnCNN图像盲降噪与优化算法对比
浏览次数: 1405
叉乘
浏览次数: 1263
2021牛客暑期多校训练营1 B题 Ball Dropping
浏览次数: 1035

二分图匹配（匈牙利算法）

Osilly • 2021 年 04 月 19 日

1.什么是二分图？

2.我们二分图一般需要我们处理什么样的问题？

3.二分图最大匹配算法

4.匈牙利算法

关于匈牙利算法的解析，这篇博客学习起来会有很大的帮助
一个超棒的匈牙利算法解析
本文对算法一些细节部分进行解释
首先，上代码

int dfs(int x) {
  for (int i = 1; i <= m; i++) {
    if (line[x][i] == 1 && used[i] == 0) {
      used[i] = 1;
      if (match[i] == 0 || dfs(match[i])) {
        match[i] = x;
        return 1;
      }
    }
  }
  return 0;
}

for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }

这两部分便是代码的核心
匈牙利算法核心就是尽可能寻找新的增广路
这里借助下上面博客的图

算法的运行过程

我们如果要最大的配对数，按照算法的运行

第一步

for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }

这个match数组非常重要，不仅仅是记录女生的配对对象，同样标记女生有没有被匹配过，最为重要的，它作为之后算法回溯的指引

这里显然可以看出选择1号女生
同理，第二次循环查询2号男生时，同样找到了2号女生

第二步

used的数组的作用就在这里体现，来记录本次dfs中女生是否被查询过，查询过就不再重复查询

1号男生查询到了2号女生，很可惜，二号女生也被2号男生配对过了，但我们仍然不放弃，继续重复看一看二号男生可不可以找个新的配对

第三步

第四步

算法的核心

上面就是算法的详细运行情况，算法的核心就是，我们在不减少原先配对的数量的同时（可以改变关系但不减少数量），增加一个新的配对

二分图的一些例题

第一个自然是模板题
洛谷的P3386 【模板】二分图最大匹配

https://www.luogu.com.cn/problem/P3386

贴出代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 5e2 + 10;

int n, m, e;
int line[maxn][maxn];
int used[maxn];
int U[maxn];
int u, v;
int ans;

int dfs(int x) {
  for (int i = 1; i <= m; i++) {
    if (line[x][i] == 1 && used[i] == 0) {
      used[i] = 1;
      if (U[i] == 0 || dfs(U[i])) {
        U[i] = x;
        return 1;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m >> e;
  for (int i = 1; i <= e; i++) {
    cin >> u >> v;
    line[u][v] = 1;
  }
  for (int i = 1; i <= n; i++) {
    memset(used, 0, sizeof(used));
    if (dfs(i)) ans++;
  }
  cout << ans;
  return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 8e3 + 10;

int T;
int match[maxn], used[maxn];
int line[maxn][maxn];
int e[maxn][maxn];
int v[maxn], u[maxn];
int k1, k2;
int a, b, m;
int ans;
vector<int> vec1, vec2;  // 1 prime

int check(int x) {
  int re = 0;
  while (x) {
    if (x & 1) re++;
    x /= 2;
  }
  if (re % 2 == 0)
    return 1;
  else
    return 0;
}

void init() {
  for (int i = 1; i <= b; i++) {
    for (int j = 1; j <= b; j++) {
      if (v[i] % 2 == 1 && v[j] % 2 == 0 && check(v[i] | v[j])) {  
        e[i][j] = 1;
      }
    }
  }
}

int dfs(int x) {
  for (int i = 0; i < vec2.size(); i++) {
    if (e[vec1[x]][vec2[i]] == 1 && used[vec2[i]] != k1) {
      used[vec2[i]] = k1;
      if (match[vec2[i]] == 0 || dfs(match[vec2[i]])) {
        match[vec2[i]] = vec1[x];
        return 1;
      }
    }
  }
  return 0;
}

void add1(int x, int y) {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    int re = 0;
    if (line[x][i] == 1) re++;
    if (line[y][i] == 1) re++;
    if (re == 2) {
      if (v[i] % 2 == 1)
        vec1.push_back(i);
      else
        vec2.push_back(i);
    }
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum + 2);
}

void add2(int x) {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    if (line[x][i] == 1) {
      if (v[i] % 2 == 1)
        vec1.push_back(i);
      else
        vec2.push_back(i);
    }
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum + 1);
}

void add3() {
  int sum = 0;
  vec1.clear();
  vec2.clear();
  fill(match, match + maxn, 0);
  for (int i = 1; i <= b; i++) {
    if (v[i] % 2 == 1)
      vec1.push_back(i);
    else
      vec2.push_back(i);
  }
  for (int i = 0; i < vec1.size(); i++) {
    // k1时间戳
    k1++;
    if (dfs(i)) sum++;
  }
  ans = max(ans, (int)(vec1.size() + vec2.size()) - sum);
}

int main() {
  cin >> T;
  while (T--) {
    vec1.clear();
    vec2.clear();
    ans = 0;
    k1 = 0;
    memset(used, 0, sizeof(used));
    cin >> a >> b >> m;
    for (int i = 1; i <= a; i++) cin >> u[i];
    for (int i = 1; i <= b; i++) cin >> v[i];
    for (int i = 1; i <= m; i++) {
      int x, y;
      cin >> x >> y;
      line[x][y] = 1;
    }
    // k2 = 2;//代表无关系
    init();
    for (int i = 1; i <= a; i++) {
      for (int j = i+1; j <= a; j++) {
        if ((u[i] % 2) != (u[j] % 2)) add1(i, j);
      }
    }
    for (int i = 1; i <= a; i++) {
      add2(i);
    }
    add3();
    cout << ans << endl;
  }
  return 0;
}

第三题牛客的Graph Coloring I

https://ac.nowcoder.com/acm/problem/19790

一道经典的二分图判断题，这道题的难点和创新处在于奇数环的路径还原

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;

vector<int> vec[maxn];
int n, m;
int u, v;
int pre[maxn];
int color[maxn];
int flag = 0;
int k;
int used[maxn];

int dfs(int s, int c) {
  color[s] = c;
  for (int i = 0; i < vec[s].size(); i++) {
    if (color[vec[s][i]] == c) {
      pre[vec[s][i]] = s;
      k = s;
      return 0;
    }
    if (color[vec[s][i]] == 0 && !dfs(vec[s][i], -c)) {
      if (!pre[vec[s][i]]) pre[vec[s][i]] = s;
      return 0;
    }
  }
  return 1;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  if (dfs(1, 1)) {
    cout << '0' << endl;
    for (int i = 1; i <= n; i++) {
      if (color[i] == 1)
        cout << 0 << ' ';
      else
        cout << 1 << ' ';
    }
  } else {
    int sum = 0;
    int v = k;
    while (pre[v] != k) {
      v = pre[v];
      sum++;
    }
    cout << sum + 1 << endl;
    v = k;
    while (pre[v] != k) {
      cout << v << ' ';
      v = pre[v];
    }
    cout << v;
  }
  return 0;
}

二分图匹配（匈牙利算法）

1.什么是二分图？

2.我们二分图一般需要我们处理什么样的问题？

3.二分图最大匹配算法

4.匈牙利算法

算法的运行过程

第一步

第二步

第三步

第四步

算法的核心

二分图的一些例题

2 条评论

发表评论取消回复

typora配合Lsky pro+PicGo实现图片一键上传到自己服务器同时获得外链

CycleGAN、StarGAN、AGGAN、AttentionGAN、U-GAT-IT网络特点总结

二分图匹配（匈牙利算法）

带花树算法（一般图匹配）

GANs学习笔记

7-1 初识Redis

2-5 java 和 MongoDB

DnCNN图像盲降噪与优化算法对比

叉乘

2021牛客暑期多校训练营1 B题 Ball Dropping

二分图匹配（匈牙利算法）

1.什么是二分图？

2.我们二分图一般需要我们处理什么样的问题？

3.二分图最大匹配算法

4.匈牙利算法

算法的运行过程

第一步

第二步

第三步

第四步

算法的核心

二分图的一些例题

1.什么是二分图？

2.我们二分图一般需要我们处理什么样的问题？

3.二分图最大匹配算法

4.匈牙利算法

算法的运行过程

第一步

第二步

第三步

第四步

算法的核心

二分图的一些例题

2 条评论

发表评论 取消回复

二分图匹配（匈牙利算法）

1.什么是二分图？

2.我们二分图一般需要我们处理什么样的问题？

3.二分图最大匹配算法

4.匈牙利算法

算法的运行过程

第一步

第二步

第三步

第四步

算法的核心

二分图的一些例题

发表评论取消回复