一、二分图模板
二分图的性质：
- 集合内部没有边
- 二分图当且仅当图中不含奇数环
1.1. 染色法判断是否为二分图
简要介绍
采用 $dfs$ 遍历图。尝试把和一个点相连的所有的点涂为不同色（一共两种颜色）。
什么情况下图不是二分图呢？尝试涂色时相邻点已被涂同样的颜色。
模板
//尝试将u染成col 的同时尝试拓展它的临边
bool dfs(int u, int col)
{
color[u] = col;
//处理和当前所有相连的点
for(int i = 0; i < a[u].size(); ++ i)
{
if(!color[a[u][i]] && !dfs(a[u][i], 3 - col)) return false; //尝试将它的临边染成2
if(color[a[u][i]] == col) return false; //如果它和临边颜色相同的话false
}
return true;
}
bool solve()
{
//遍历每一个点，尝试将其涂色
for(int i = 1; i <= n; ++ i)
if(!color[i])
if(!dfs(i, 1)) return false; //还没有被染色,尝试将其染成1
return true;
}1.2. 匈牙利算法求二分图的最大匹配数
简要介绍
别名：月老红线算法
对每一个男生尝试匹配他暗恋的女生。如果该女生名花无主：皆大欢喜；但是如果该女生名花有主，这个算法的哲学气息就体现出来了：如果该女生的现对象有备胎的话：强行把男友劈腿给备胎！
模板
bool find(int u)
{
//对于该男生的所有暗恋对象而言 如果名花无主或可以成功绿别人:true
for(int &i: a[u])
{
if(!st[i]) //没有尝试过给该女生修改对象
{
st[i] = true;
if(!match[i] || find(match[i])) //名花无主 或 男友劈腿
{
match[i] = u;
return true;
}
}
}
return false;
}
//main 函数
for(int i = 1; i <= n1; ++ i)
{
memset(st, 0, sizeof st); //st的意义是对女生尝试过换人 需要对每个男生清空
if(find(i)) res ++;
}二、例题(点击题目跳转链接)
按照传统先上两题板子供读者自测；再上一道非模板题。
2.1. 染色法判定二分图
参考代码
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
vector<int> color;
int n, m;
//尝试将u染成col 的同时尝试拓展它的临边
bool dfs(int u, int col)
{
color[u] = col;
for(int i = 0; i < a[u].size(); ++ i)
{
if(!color[a[u][i]] && !dfs(a[u][i], 3 - col)) return false; //尝试将它的临边染成2
if(color[a[u][i]] == col) return false; //如果它和临边颜色相同的话false
}
return true;
}
bool solve()
{
for(int i = 1; i <= n; ++ i)
if(!color[i])
if(!dfs(i, 1)) return false; //还没有被染色,尝试将其染成1
return true;
}
int main()
{
cin >> n >> m;
a.resize(n + 1); color.resize(n + 1);
int x, y;
for(int i = 0; i < m; ++ i)
{
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
bool t = solve();
cout << (t ? "Yes" : "No");
return 0;
}2.2. 二分图的最大匹配
参考代码
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
const int N = 505;
int match[N];
bool st[N];
bool find(int u)
{
//对于该男生的所有暗恋对象而言 如果名花无主或可以成功绿别人:true
for(int &i: a[u])
{
if(!st[i]) //没有尝试过给该女生修改对象
{
st[i] = true;
if(!match[i] || find(match[i])) //名花无主 或 男友劈腿
{
match[i] = u;
return true;
}
}
}
return false;
}
int main()
{
int n1, n2, m; cin >> n1 >> n2 >> m;
a.resize(n1 + 1);
int x, y;
for(int i = 0; i < m; ++ i)
{
cin >> x >> y;
a[x].push_back(y);
}
int res = 0;
for(int i = 1; i <= n1; ++ i)
{
memset(st, 0, sizeof st);
if(find(i)) res ++;
}
cout << res;
return 0;
}2.3. 机器任务
有两台机器 A，B 以及 K 个任务。
机器 A 有 N 种不同的模式（模式 0∼N−1），机器 B 有 M 种不同的模式（模式 0∼M−1）。
两台机器最开始都处于模式 0。
每个任务既可以在 A 上执行，也可以在 B 上执行。
对于每个任务 i，给定两个整数 a[i] 和 b[i]，表示如果该任务在 A 上执行，需要设置模式为 a[i]，如果在 B 上执行，需要模式为 b[i]。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 N,M,K。
接下来 K 行，每行三个整数 i,a[i] 和 b[i]，i 为任务编号，从 0 开始。
当输入一行为 0 时，表示输入终止。
输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。
数据范围
N,M<100,K<1000
0≤a[i]<N
0≤b[i]<M
输入样例：
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0输出样例：
3题目分析
- 所有的任务都要被做完，即所有的边都要被覆盖。
- 用最少的点覆盖所有的边。
- Konig定理：求最小的点数转化成求二分图的最大匹配数。
题目分析中的 3 已将 konig 定理证明。这里蒟蒻重述一遍自己的理解。观众可直接跳过。
左边集合标男；右边集合标女。男女之间的连线表示喜欢关系。
月老牵线算法会尝试为每一个男的匹配对象。对于每一个男的而言，结果只有两个：
-
转正：
- 妹子一开始也单身。
- 绿了别人，被绿的人和备胎在一起了。
-
依旧单身狗：
- 本来就没人喜欢他。
- 他喜欢的妹子名花有主，且没有绿成功，而没有绿成功的原因是妹子对象没有备胎。
在依旧单身狗的情况中已经尝试为他找对象了。这说明如果他身上有红线、那么有妹子是喜欢他的，即他可以被已经名花有主的点到达；如果他身上没红线、不需要被考虑。
经过月老算法后：大结局是所有的男的都尝试过找对象了、并且是用尽了一切手段。单身狗由暗恋对象做源点、非单身的自己为源点。这些源点组合起来能覆盖所有的边。
参考代码
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
const int N = 105;
bool st[N];
int dist[N];
bool find(int u)
{
for(int &i : a[u])
{
if(!st[i])
{
st[i] = true;
if(!dist[i] || find(dist[i]))
{
dist[i] = u;
return true;
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
int n, m, k;
while(cin >> n >> m >> k && n)
{
memset(dist, 0, sizeof dist);
a.clear();
a.resize(n + 1);
int x, y, z;
for(int i = 0; i < k; ++ i)
{
cin >> x >> y >> z;
if(!y || !z) continue;
a[y].push_back(z);
}
int res = 0;
for(int i = 1; i <= n; ++ i)
{
memset(st, 0, sizeof st);
if(find(i)) res ++ ;
}
cout << res << endl;
}
return 0;
}小结
- 匈牙利算法真的好有意思啊，嚯嚯嚯哈哈哈哈哈
- 染色法用的 dfs，只有没被染色才能进入 dfs 中
- koing 定理：二分图的最大匹配也是二分图的最少的点覆盖它的所有边