===
Index
简介
如果一张无向图的N个节点可以分成两个不相交的非空集合，并且同一集合内的点没有边相连，那么称该无向图为二分图.
判定定理
- 二分图不存在长度为奇数的环
因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。
二分图判定
染色法
时间复杂度 O(n+m)
dfs
bool isBipartite(vector<vector<int>>& g) {
int n = g.size();
vector<int> color(n);
function<bool(int, int)> dfs = [&](int u, int c) {
color[u] = c;
for (int v: g[u]) {
if (!color[v]) {
if (!dfs(v, 3 - c)) return false;
}else if (color[v] == c) return false;
}
return true;
};
for (int i = 0; i < n; i++)
if (!color[i] && !dfs(i, 1)) return false;
return true;
}
bfs
bool isBipartite(vector<vector<int>>& g) {
int n = g.size();
vector<int> color(n);
queue<int> q;
for (int i = 0; i < n; ++i) {
if (!color[i]) {
q.push(i);
color[i] = 1;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &v: g[u]) {
if (!color[v]) {
q.push(v);
color[v] = 3 - color[u];
} else if (color[v] == color[u]) return false;
}
}
}
return true;
}
并查集判定
我们知道如果是二分图的话，那么图中每个顶点的所有邻接点都应该属于同一集合，且不与顶点处于同一集合。因此我们可以使用并查集来解决这个问题，我们遍历图中每个顶点，将当前顶点的所有邻接点进行合并，并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了，若是，则说明不是二分图。
struct DSU {
public:
DSU() : _n(0) {}
explicit DSU(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = get(a), y = get(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return get(a) == get(b);
}
int get(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = get(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[get(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = get(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
bool isBipartite(vector<vector<int>>& g) {
int n = g.size();
DSU d(n);
for (int i = 0; i < n; ++i) {
for (auto &v : g[i]) {
if (d.same(i, v)) return false;
d.merge(g[i][0], v);
}
}
return true;
}
二分图最大匹配
设G为二分图，若在G的子图M中，任意两条边都没有公共节点，那么称M为二分图G的一组匹配，在二分图中，包含边数最多的一组匹配成为二分图的最大匹配。
交替路
从一个未匹配点出发，以此经过非匹配边、匹配边、非匹配边…,形成的路径叫做交替路.
增广路
从一个未匹配点出发，走交替路，若能到达另一个未匹配点，则这条交替路称为增广路。
增广路中非匹配边比非匹配边多一条，只要将增光路中匹配边和非匹配边交换，交换后，图中的匹配边数目比原来多了一条。 这里的增广路就是能增加匹配边的一条交替路。
匈牙利算法
时间复杂度： O(n*m)
// g只需要加单向边，男选女
// 顶点编号从0开始 n1为男生的数目
int maxMatch(vector<vector<int>> &g,int n1) {
int n = g.size(), ans = 0;
vector<int> vis(n), f(n, -1);
function<bool(int)> dfs = [&](int u) {
for(auto& v: g[u]) {
if(vis[v]) continue;
vis[v] = 1;
if (f[v] == -1 || dfs(f[v])) {
f[v] = u;
return true;
}
}
return false;
};
for (int i = 0; i < n1; ++i) {
vis.assign(n, 0);
if (dfs(i)) ans++;
}
return ans;
}
hopcroftkarp
Hopcroft–Karp算法可以在 O((n+m)*sqrt(n)) 时间求二分图等最大匹配。
模板
struct BipMatching {
static constexpr int ABSENT = -1;
int _n, _m;
vector<int> _to_r, _to_l;
vector<vector<int>> _g;
int _f = 0;
BipMatching() {}
BipMatching(int n, int m) : _n(n), _m(m), _to_r(_n, ABSENT), _to_l(_m, ABSENT), _g(n + m) {}
void add_edge(int from, int to) { _g[from].push_back(to), _f = -1;}
template <bool shuffle = true>
int solve_heuristics() {
if (_f >= 0) return _f;
static std::mt19937 rng(std::random_device{}());
if constexpr (shuffle) for (auto& adj : _g) std::shuffle(adj.begin(), adj.end(), rng);
vector<int8_t> vis(_n, false);
auto dfs = [&, this](auto dfs, int u) -> bool {
if (std::exchange(vis[u], true)) return false;
for (int v : _g[u]) if (_to_l[v] == ABSENT) return _to_r[u] = v, _to_l[v] = u, true;
for (int v : _g[u]) if (dfs(dfs, _to_l[v])) return _to_r[u] = v, _to_l[v] = u, true;
return false;
};
for (bool upd = true; std::exchange(upd, false);) {
vis.assign(_n, false);
for (int i = 0; i < _n; ++i) if (_to_r[i] == ABSENT) upd |= dfs(dfs, i);
}
return _f = _n - std::count(_to_r.begin(), _to_r.end(), ABSENT);
}
int solve_maxflow() {
if (_f >= 0) return _f;
const auto h = reversed_graph();
vector<int> level(_n + _m), iter(_n + _m);
deque<int> que;
auto bfs = [&] {
for (int i = 0; i < _n; ++i) {
if (_to_r[i] == ABSENT) level[i] = 0, que.push_back(i);
else level[i] = -1;
}
fill(level.begin() + _n, level.end(), -1);
bool ok = false;
while (not que.empty()) {
int v = que.front();
que.pop_front();
for (int r : _g[v]) if (_to_r[v] != r and level[_n + r] < 0) {
const int l = _to_l[r];
level[_n + r] = level[v] + 1;
if (l == ABSENT) ok = true;
else if (level[l] < 0) level[l] = level[v] + 2, que.push_back(l);
}
}
return ok;
};
auto dfs = [&](auto dfs, const int r) -> bool {
const int level_v = level[_n + r];
if (level_v < 0) return false;
const int dr = h[r].size();
for (int &i = iter[_n + r]; i < dr; ++i) {
const int l = h[r][i];
if (level_v <= level[l] or _to_l[r] == l or iter[l] > _m) continue;
if (int r2 = _to_r[l]; r2 == ABSENT) {
iter[l] = _m + 1, level[l] = _n + _m;
_to_r[l] = r, _to_l[r] = l;
return true;
} else if (iter[l] <= r2) {
iter[l] = r2 + 1;
if (level[l] > level[_n + r2] and dfs(dfs, r2)) {
_to_r[l] = r, _to_l[r] = l;
return true;
}
iter[l] = _m + 1, level[l] = _n + _m;
}
}
return level[_n + r] = _n + _m, false;
};
int flow = 0;
while (bfs()) {
fill(iter.begin(), iter.end(), 0);
for (int j = 0; j < _m; ++j) if (_to_l[j] == ABSENT) flow += dfs(dfs, j);
}
return _f = flow;
}
int solve() { return solve_maxflow();}
vector<pair<int, int>> max_matching() { // 最大匹配
if (_f < 0) solve();
vector<pair<int, int>> res;
res.reserve(_f);
for (int i = 0; i < _n; ++i) if (_to_r[i] != ABSENT) res.emplace_back(i, _to_r[i]);
return res;
}
vector<pair<int, int>> min_edge_cover() { //最小路径覆盖
auto res = max_matching();
vector<bool> vl(_n, false), vr(_n, false);
for (const auto& [u, v] : res) vl[u] = vr[v] = true;
for (int u = 0; u < _n; ++u) for (int v : _g[u]) if (not (vl[u] and vr[v])) {
vl[u] = vr[v] = true;
res.emplace_back(u, v);
}
return res;
}
vector<int> min_vertex_cover() { //最小点覆盖
if (_f < 0) solve();
vector<vector<int>> g(_n + _m);
vector<bool> cl(_n, true), cr(_m, false);
for (int u = 0; u < _n; ++u) for (int v : _g[u]) {
if (_to_r[u] == v) {
g[v + _n].push_back(u);
cl[u] = false;
} else {
g[u].push_back(v + _n);
}
}
vector<bool> vis(_n + _m, false);
deque<int> dq;
for (int i = 0; i < _n; ++i) if (cl[i]) {
dq.push_back(i);
vis[i] = true;
}
while (dq.size()) {
int u = dq.front();
dq.pop_front();
for (int v : g[u]) {
if (vis[v]) continue;
vis[v] = true;
(v < _n ? cl[v] : cr[v - _n]) = true;
dq.push_back(v);
}
}
vector<int> res;
for (int i = 0; i < _n; ++i) if (not cl[i]) res.push_back(i);
for (int i = 0; i < _m; ++i) if (cr[i]) res.push_back(_n + i);
return res;
}
vector<int> max_independent_set() {
vector<bool> use(_n + _m, true);
for (int v : min_vertex_cover()) use[v] = false;
vector<int> res;
for (int i = 0; i < _n + _m; ++i) if (use[i]) res.push_back(i);
return res;
}
int left_size() const { return _n; }
int right_size() const { return _m; }
pair<int, int> size() const { return { _n, _m }; }
int right(int l) const { assert(_f >= 0); return _to_r[l]; }
int left(int r) const { assert(_f >= 0); return _to_l[r]; }
const auto graph() const { return _g; }
vector<vector<int>> reversed_graph() const {
vector<vector<int>> h(_m);
for (int i = 0; i < _n; ++i) for (int j : _g[i]) h[j].push_back(i);
return h;
}
};
使用方法
- 定义一个最大匹配
BipMatching g(n, m); // 一边n个节点，另一边m个节点
- 添加边(u, v)
g.add_edge(u, v); // 0 < u < n, 0 < v < m
- 求最大匹配
auto p = g.max_matching();
cout << p.size() << '\n'; // p.size()表示最大匹配的值
for (const auto &[u, v] : p) { // 具体的匹配结果
cout << u << ' ' << v << '\n';
}
- 最小路径覆盖
auto p = g.min_edge_cover();
cout << p.size() << '\n'; // p.size()表示最小路径覆盖的值
for (const auto &[u, v] : p) { // 具体的覆盖结果
cout << u << ' ' << v << '\n';
}
- 最小点覆盖
auto p = g.min_vertex_cover();
cout << p.size() << '\n'; // p.size()表示最小点覆盖的值
for (const auto &u : p) { // 具体的覆盖结果
cout << u << '\n';
}
- 最大独立集
auto p = g.max_independent_set();
cout << p.size() << '\n'; // p.size()表示最大独立集的值
for (const auto &u : p) { // 具体的最大独立集
cout << u << '\n';
}
二分图的最大匹配
给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。 数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
#include <bits/stdc++.h>
using namespace std;
int maxMatch(vector<vector<int>> &g,int n1) {
int n = g.size(), ans = 0;
vector<int> vis(n), f(n, -1);
function<bool(int)> dfs = [&](int u) {
for(auto& v: g[u]) {
if(vis[v]) continue;
vis[v] = 1;
if (f[v] == -1 || dfs(f[v])) {
f[v] = u;
return true;
}
}
return false;
};
for (int i = 0; i < n1; ++i) {
vis.assign(n, 0);
if (dfs(i)) ans++;
}
return ans;
}
int n,m,x,y,k,q;
void solve(){
int n1,n2,m;
cin>>n1>>n2>>m;
int n = max(n1,n2);
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >>u >> v;
u--,v--;
g[u].push_back(v);
}
int ans = maxMatch(g,n1);
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(20);
solve();
return 0;
}
dinic算法
二分图最大匹配是网络流的特殊形式。
假设左半边的点集为G, 右半边的点集为M, 从起点到G连一条长度为1的边, 从M到终点连一条长度为1的边 ,从G到M连一条长度为1的边。 后跑一遍最大流dinic算法 即为所求的二分图的最大匹配
二分图最大权完美匹配
给定一张带边权的二分图，其左部、右部点数相等，均为n个点，如果最大匹配有n条边，则称二分图的完美匹配。 二分图边权和最大的完美匹配，称二分图的最大权完美匹配
KM 算法
时间复杂度 O(n^3)
// w:vector w(n + 1,vector<long long>(n + 1, -inf)); 权重矩阵
// 顶点下标从1-n.
// 需要满足存在完美匹配条件，每个点的相匹配点记录在f数组
const long long inf = 1e18;
long long KM(vector<vector<long long>> &w) {
int n = w.size(); // 定点数为n-1个，1 - (n-1)
vector<long long> ex(n), ey(n);
vector<int> f(n, -1);
auto bfs = [&](int u) {
vector<int> vy(n), pre(n, -1);
vector<long long> slack(n, inf);
long long x, y = 0, yy = 0, d;
f[y] = u;
while (1) {
x = f[y], d = inf, vy[y] = 1;
for (int i = 1; i < n; ++i) {
if (vy[i]) continue;
if (slack[i] > ex[x] + ey[i] - w[x][i]) {
slack[i] = ex[x] + ey[i] - w[x][i];
pre[i] = y;
}
if (slack[i] < d) {
d = slack[i], yy = i;
}
}
for (int i = 0; i < n; ++i) {
if (vy[i]) ex[f[i]] -= d, ey[i] += d;
else slack[i] -= d;
}
y = yy;
if (f[y] == -1) break;
}
while (y) {
f[y] = f[pre[y]];
y = pre[y];
}
};
for (int i = 1; i < n; ++i) bfs(i);
long long res = 0;
for (int i = 1; i < n; ++i)
if(f[i] != -1) res += w[f[i]][i];
return res;
}
模板二分图最大权完美匹配
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long inf = 1e18;
long long KM(vector<vector<long long>> &w) {
int n = w.size();
vector<long long> ex(n), ey(n);
vector<int> f(n, -1);
auto bfs = [&](int u) {
vector<int> vy(n), pre(n, -1);
vector<long long> slack(n, inf);
long long x, y = 0, yy = 0, d;
f[y] = u;
while (1) {
x = f[y], d = inf, vy[y] = 1;
for (int i = 1; i < n; ++i) {
if (vy[i]) continue;
if (slack[i] > ex[x] + ey[i] - w[x][i]) {
slack[i] = ex[x] + ey[i] - w[x][i];
pre[i] = y;
}
if (slack[i] < d) {
d = slack[i], yy = i;
}
}
for (int i = 0; i < n; ++i) {
if (vy[i]) ex[f[i]] -= d, ey[i] += d;
else slack[i] -= d;
}
y = yy;
if (f[y] == -1) break;
}
while (y) {
f[y] = f[pre[y]];
y = pre[y];
}
};
for (int i = 1; i < n; ++i) bfs(i);
long long res = 0;
for (int i = 1; i < n; ++i)
if(f[i] != -1) res += w[f[i]][i];
cout << res << "\n";
for (int i = 1; i < n; ++i) {
cout << f[i] << " \n"[i==n];
}
return res;
}
int main() {
int n, m;
scanf("%d%d",&n,&m);
vector w(n + 1,vector<long long>(n + 1, -inf));
for (int i = 0; i < m; ++i) {
ll x, y, z;
scanf("%lld%lld%lld",&x,&y, &z);
w[x][y] = z;
}
KM(w);
return 0;
}
二分图常见模型
dag最小路径覆盖
m名客人从城市不同位置出发，达到目的地，已知每个人的出发时间，出发地点和目的地，你的任务是用最少的出租车送他们。从一个点到另一个点的所用时间是他们的曼哈顿距离。接送某乘客要提前到一分钟。
- 0 < m < 500
分析
这个DAG最小路径覆盖经典问题，可以把这n个乘客构造成一张二分图，如果在接送完A乘客还有时间接送B乘客，就在二分图中连接一条从A到B的边。然后最小路径覆盖的答案就是n（乘客总数）-最大匹配。 证明：把每个乘客对应一个车，如果在二分图中ab乘客有边，那么意味车的数目就可以减少一个，当然车的数目越少越好，所以就是匹配数目越多越好。
int maxMatch(vector<vector<int>> &g,int n1) {
int n = g.size(), ans = 0;
vector<int> vis(n), f(n, -1);
function<bool(int)> dfs = [&](int u) {
for(auto& v: g[u]) {
if(vis[v]) continue;
vis[v] = 1;
if (f[v] == -1 || dfs(f[v])) {
f[v] = u;
return true;
}
}
return false;
};
for (int i = 0; i < n1; ++i) {
vis.assign(n, 0);
if (dfs(i)) ans++;
}
return ans;
}
void solve() {
int n;
scanf("%d", &n);
vector<array<int, 5>> a(n);
for (int i = 0; i < n; ++i ) {
int t1, t2;
scanf("%d:%d%d%d%d%d", &t1, &t2, &a[i][1], &a[i][2],&a[i][3],&a[i][4]);
a[i][0] =t1 * 60 + t2;
}
auto chk = [&](int u, int v) {
if (a[u][0] > a[v][0]) swap(u, v);
int t1 = a[u][0], t2 = a[v][0], c1 = abs(a[u][1] - a[u][3]) + abs(a[u][2] - a[u][4]);
if (t1 + c1 + abs(a[u][3] - a[v][1]) + abs(a[u][4] - a[v][2]) < t2) return true;
return false;
};
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
if (chk(i, j)) {
g[i].push_back(j);
}
}
cout << n - maxMatch(g, n) << '\n';
}
二分图最小点覆盖
二分图G=(X,Y,E), 求最小点集S，使得任一条边都有至少一个端点属于S，S称为最小点覆盖。 最小点覆盖大小等于最大匹配
有两台机器A,B，A有n种不同模式,B有m种不同模式，有k个任务，每个任务可以在机器A或B上的特定模式运行，每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。求机器重启的最小次数。
- 0 < n, m < 100
- 0 < k < 1000
分析
构图： X = {机器A的集合}， Y = {机器B的集合} 如果有任务由机器A的i模式或机器B的j模式完成，在 i, j节点连接一条边。这样就构造了一个二分图
求二分图的最小点覆盖。
#include <bits/stdc++.h>
using namespace std;
int maxMatch(vector<vector<int>> &g,int n1) {
int n = g.size(), ans = 0;
vector<int> vis(n), f(n, -1);
function<bool(int)> dfs = [&](int u) {
for(auto& v: g[u]) {
if(vis[v]) continue;
vis[v] = 1;
if (f[v] == -1 || dfs(f[v])) {
f[v] = u;
return true;
}
}
return false;
};
for (int i = 0; i < n1; ++i) {
vis.assign(n, 0);
if (dfs(i)) ans++;
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k;
while (cin >> n && n) {
cin >> m >> k;
vector<vector<int>> g(n + m);
for (int i = 0, j, u, v; i < k; ++i) {
cin >> j >> u >> v;
u--, v--;
g[u].push_back(v + n);
}
cout << maxMatch(g, n) << '\n';
}
return 0;
}
二分图最大独立集
在二分图中尽量选择多的点，任意两点不相邻，最大独立集于最小点覆盖是互补的， 最大独立集的数目等于总节点数减去最大匹配数，最小点覆盖中已选点与未选点互换，就可以得到最大独立集。
