二分图 - 定义

二分图是一种特殊的无向图,可以将点集划分为两部分,在同一集合中的节点之间没有 edge。

二分图 - 性质

  1. 二分图 $\iff$ 图中没有奇环(指节点个数为奇数的环) $\iff$ 可以进行二分图染色

二分图染色

给定一个二分图,我们可以仅用两种颜色将每个节点染上色,并且保证每个 edge 的两端颜色一定不同。

同理,如果一个图可以进行二分图染色,那么它就是一个二分图(这用于 判断一个图是否为二分图

染色的方法:用 DFS 即可。(记得要从每个节点都开始 DFS 一次)

  1. 随机选择一个点 $u$ 作为出发点,它的颜色为 $c_u = 0$。
  2. 看它的 neighbor $v$ 的颜色,如果等于 $c_u$ ^ $1$,或者没染色,就染成 $c_u$ ^ $1$。否则的话产生冲突,说明这不是二分图。

例题

例1 CF741C Arpa’s overnight party and Mehrdad’s silent entering

题意

给定 $n$ 对情侣 $(a_i, b_i)$($a_i, b_i \in [1,2n]$),总共有 $2n$ 个人,每个人的编号是从 $1$ 到 $2n$。现在有 $2$ 种食物($1$ 或者 $2$),求一种分配方式使得:

  1. 每对情侣 $(a_i, b_i)$ 不能吃同一种食物。
  2. 相邻的 $3$ 个编号,食物不能完全相同。(编号是环形的,这意味着 $2n, 1, 2$ 也算是相邻的 $3$ 个人)。

如果无解,输出 $-1$。

其中,$1 \leq n \leq 10^5$。

题解

每对情侣 $(a_i, b_i)$ 的食物不同,让我们想到二分图。但是第二个条件怎么办?

直觉上来说,这个题一定是有解的。

所以,我们可以做一个特殊的限制,直接强制 $2i-1, 2i$ 的食物不同,这个条件就满足了。

接下来我们要证明,将第二个限制条件转化以后,仍然有解。


对于这个模型建图,将每个人作为一个节点,每对情侣 $(a_i, b_i)$ 作为一条边连起来。然后再将 $(2i-1, 2i)$ 作为一条边连起来。

那么只要这个图是二分图,就有解。(因为二分图保证了每条边两端的颜色不同)

如果图中有环,那么必然是由 $x$ 对情侣组成的一个环。所以环的节点数量为 $2x$。所以不可能有奇环。所以这个图是二分图。

所以建完图以后,跑一个二分图染色即可。

• 注意,二分图染色的 DFS 要从每一个节点都开始一次。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxm = 1e6;

int n;
struct Edge {
    int to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
int color[maxn];

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
int a[maxn], b[maxn];
bool vis[maxn];
void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        color[to] = color[u] ^ 1;
        dfs(to);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        addEdge(a[i], b[i]);
        addEdge(b[i], a[i]);
    }
    for (int i = 1; i <= 2*n; i+=2) {
        addEdge(i, i+1);
        addEdge(i+1, i);
    }
    vis[1] = 1;
    for (int i = 1; i <= 2*n; i++) dfs(i);
    for (int i = 1; i <= n; i++) {
        if (!color[a[i]]) cout << 2 << " ";
        else cout << 1 << " ";

        if (!color[b[i]]) cout << 2 << "\n";
        else cout << 1 << "\n";
    }
}

例2 CF553C Love Triangles

题意

给定 $n$ 个人,每两个人之间,要么互相love,要么互相hate。

现在已知 $m$ 个关系,每个关系的格式为 $a ~ b ~ c$,代表 $a$ 和 $b$ 互相 love($c = 1$),或者互相 hate($c = 0$)。

请求出,有多少个方案使得整个关系网满足以下条件(答案对 $10^9+7$ 取模)

对于任意三个人 $a,b,c$,要么这三个人互相 love,要么 $a,b$ 互相love,而 $a,c$ 和 $b,c$ 互相hate。

其中,$3 \leq n \leq 10^5, 0 \leq m \leq 10^5$

题解

首先我们会发现,love是有传递性的:如果 $a,b$ 互相love,$b,c$ 互相love,那么根据定义,一定有 $a,c$ 互相love。

所以对于love的关系,我们可以求出一个连通块,使得这个块内每个人互相love,那就可以缩点了。(当然需要注意的是 hate 不具有传递性)。

于是,我们只需要考虑一下 hate 怎么处理。


先放一个结论:

如果我们把这个问题考虑为图染色问题,那么两个互相hate,说明颜色不同。而互相love,说明颜色相同。

如果存在一个合法的染色方式,则说明有解。(本质上是二分图染色,互相love的在同一侧,互相hate的在两侧)

证明:存在染色方式 $\rightarrow$ 有解:

任取三个节点 $a,b,c$,有两种情况:

  1. $a,b,c$ 在同一侧,所以满足 $a,b,c$ 互相love。
  2. $a,b$ 在同一侧,$c$ 在另外一侧。这也刚好满足了 $a,b$ 互相love,而 $a,c$ 和 $b,c$ 互相hate。

证明:有解 $\rightarrow$ 存在染色方式:

根据定义染色即可,我们会发现没有冲突情况。


方案数怎么计算?

我们先进行 DFS,求出图中的连通块。

如果每个连通块内,都没有冲突情况(也就是说,每个连通块都可以做二分图染色)的话,说明有解,否则无解($ans = 0$)。

同时我们发现,对于任何一个连通块,我们只要给其中一个节点染上色,这个连通块内的其他所有节点的颜色也都确定了。

所以我们只需要给每个连通块染色即可。

设连通块的数量为 $c$,那么答案就是 $2^{c-1}$。

• 为什么不是 $2^c$?我们只要确定了第一个块的颜色,剩下的 $(c-1)$ 个块随便选颜色。我们答案是否合法,实际上与第一个块的颜色无关。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n,m;
int head[maxn], ecnt = 1, color[maxn];

struct Edge {
    int to, nxt, w;
} edges[maxn<<1];

void addEdge(int u, int v, int w) {
    Edge e = {v, head[u], w};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

ll ans = 1;
void dfs(int u) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to, w = edges[e].w;
        if (color[to] >= 0) {
            if (color[to] != (color[u] ^ w ^ 1)) ans = 0;
        } else {
            color[to] = (color[u] ^ w ^ 1);
            dfs(to);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    fill(color, color+maxn, -1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            cnt++;
            color[i] = 0;
            dfs(i);
        }
    }
    cnt--;
    for (int i = 1; i <= cnt; i++) {
        ans = ans * 2LL % mod;
    }
    cout << ans << "\n";
}

二分图匹配 - 定义

一个 匹配 的定义是一个 边集,并且这个边集中,每两个边之间没有共同的顶点。二分图的最大匹配是指 边的数量 最多的一个匹配。

二分图匹配常用的算法是 匈牙利算法 $O(nm)$,或者 最大流(dinic的复杂度为 $O(\sqrt n m)$。

匈牙利算法求最大匹配

匈牙利算法本质上是一个个求增广路(增广路指的是 从左开始,到右结束的路径,其中 左 $\rightarrow$ 右都是未匹配边,右 $\rightarrow$ 左都是匹配边)的过程。

如果我们以男女配对为例子:

对于每一个男生 $i$($i$ 在二分图的 左侧点集 中),遍历他每一个心仪的女生 $j$ ($j$ 在二分图的 右侧点集 中)(这说明 $(i,j)$ 是一条边)。那么有两种情况:

  1. 女生 $j$ 未配对,那么他们两个就配对在一起,match[j] = i
  2. 女生 $j$ 已配对,那么就让女生 $j$ 去问一下她当前的男朋友 match[j],让她男朋友尝试再换一个新的女朋友(所以就变成一个新的男生尝试配对,那么这就是一个递归的过程)。如果她男朋友成功换掉了女朋友,那么这个男生 $i$ 就可以和 女生 $j$ 配对了。否则 $i$ 就只能单着。

代码片段如下:

int n, m, adj[maxn][maxn];
int match[maxn], vis[maxn], id = 0;
// match[j] 代表女生j 当前的男朋友 i, vis[j] 代表这个女生在当前男生 i 的配对过程中,是否访问过了

bool dfs(int i) {
    for (int j = 1; j <= m; j++) {
        if (!adj[i][j] || vis[j] == id) continue;

        vis[j] = id;
        if (!match[j] || dfs(match[j])) {
            match[j] = i;
            return 1;
        }
    }
    return 0;
}

int main() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        id++;
        ans += dfs(i);
    }
}

有几个需要注意的点:

  1. 利用 int vis[] 来代表这个女生 $j$ 在当前男生 $i$ 的配对过程中,是否访问过了。(因为对于每个男生 $i$ 而言,对于每个女生 $j$ 只需要问一次即可)。
  2. 利用 id 来记录这是第几次 $dfs(i)$,然后只要判断 $vis[j]$ 是否等于 $id$ 就可以判断,本次 DFS 中是否询问过女生 $j$ 了。(这样就不用每次 DFS 结束都 memset() 一次)。

时间复杂度:每个男生都要询问所有女生,所以是 $O(nm)$(这里 $n$ 代表左边点集的数量,$m$ 代表右边点集)。

最大匹配,最小点覆盖,最大独立集,最小边覆盖

TODO

例题

例1 洛谷P1963 NOI2009 变换序列

题意

给定一个序列 $0,1,…,N-1$,我们需要求出一个变换序列 $T$,其中 $T$ 是 $0$ 到 $N-1$ 的一个 permutation。

同时,我们定义任意两个数字 $i,j$ 之间的距离 $D(i,j) = \min \{ |i-j|, N-|i-j|\}$。

现在给定原序列 和 变换序列 $T$ 之间,每个元素的距离 $D_i$,求出一个字典序最小的变换序列 $T$,如果无解,则输出 “No Answer”。

其中,$N \leq 10^4$。


样例:

Input:

5
1 1 2 2 1

Output:

1 2 4 0 3

解释:原序列是 [0,1,2,3,4],距离序列是 [1,1,2,2,1],所以最终的变换序列可能是 [0+1, 1+1, 2+2, 3-|5-2|, 4-1] = [1,2,4,0,3]

题解

原序列 作为二分图的左部分,变换序列作为二分图右部分。连边的方式就根据 距离序列 来。

例如原序列的第一个位置是 $0$,对应的距离序列第一个位置是 $1$,所以变换序列对应的值可能是 $1$ 或者 $4$。所以 $0 \rightarrow 1, 0 \rightarrow 4$ 连边即可。

连完边,跑一个最大匹配即可,如果最大匹配的数量等于 $N$ 说明有解,否则无解。


最后考虑一下 字典序最小 怎么解决?

一般来说,看到 字典序最小 就想到 贪心。所以第一个贪心思路是每次匹配的时候都 从小到大 找配对点。

然而这样有一个问题,比如 $0 \rightarrow 1$ 以后,有可能因为后续的匹配导致 $0 \rightarrow 4$。

所以我们按照编号大小,从后往前进行 DFS 即可。

for (int i = n; i >= 1; i--) {  // 注意这里是从 n 到 1
    id++;
    dfs(i);
}
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;

int match[maxn], vis[maxn], id = 0, d[maxn], n;
set<int> adj[maxn];

bool dfs(int i) {
    for (int j : adj[i]) {
        if (vis[j] == id) continue;
        vis[j] = id;
        if (!match[j]) {
            match[j] = i;
            return 1;
        }
        if (dfs(match[j])) {
            match[j] = i;
            return 1;
        }
    }
    return 0;
}

bool ok(int i) { return i >= 1 && i <= n; }

int ans[maxn];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) {
        int j = (i - d[i]);
        if (ok(j)) adj[i].insert(j);
        j = (i + d[i]);
        if (ok(j)) adj[i].insert(j);
        j = (i + (n - d[i]));
        if (ok(j)) adj[i].insert(j);
        j = (i - (n - d[i]));
        if (ok(j)) adj[i].insert(j);
    }
    for (int i = n; i >= 1; i--) {
        id++;
        dfs(i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (match[i]) cnt++;
    }
    if (cnt < n) {
        cout << "No Answer" << "\n";
    } else {
        for (int i = 1; i <= n; i++) ans[match[i]] = i;
        for (int i = 1; i <= n; i++) cout << ans[i]-1 << " ";
        cout << endl;
    }
}

例2 洛谷 P2825 [HEOI2016/TJOI2016]游戏

题意

在游戏 “泡泡堂” 中,给定一个 $n \times m$ 的网格,其中 * 代表空地,x 代表软石头,# 代表硬石头。

每个炸弹会影响它所在的行与列。炸弹可以穿透软石头,但是无法穿透硬石头。

给定一个地图,求最多放置多少个炸弹,使得每两个炸弹之间的影响范围不相交?

题解

二分图匹配的一个常见套路就是应用在 网格地图 中。

我们把 每一行 看作一个节点,每一列 也看作一个节点,而每个网格就看作一条边

如果我们不考虑硬石头的情况,那么这个题非常简单。把每个空地看作一条边,连起来以后跑一个最大匹配即可。

但是现在有硬石头。我们会发现一个硬石头可以 隔断纵向的和横向的 炸弹威力。那么,我们把硬石头隔断的部分,也看作是一个节点即可。

也就是说,现在不再是每一行/每一列作为节点,而是以 横向/纵向 线段 作为单位,每个线段是一个节点。

现在,每个网格里有 $3$ 种情况:

  1. 空地:看作一个正常的边
  2. 软石头:忽略不计
  3. 硬石头:作为分界点,上下是两个不同的线段,左右是两个不同的线段。

图建好了,再跑一个最大匹配即可。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int maxm = 2505;

int n,m;
char arr[maxn][maxn];
vector<int> adj[maxm];

int id, lcnt, rcnt;
int l[maxn][maxn], r[maxn][maxn];
int match[maxm], vis[maxm], vis_id;

bool dfs(int i) {
    for (int j : adj[i]) {
        if (vis[j] == vis_id) continue;
        vis[j] = vis_id;
        if (!match[j] || dfs(match[j])) {
            match[j] = i;
            return 1;
        }
    }
    return 0;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    id = 0;
    for (int i = 1; i <= n; i++) {
        id++;
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == '#') {
                id++;
                continue;
            }
            l[i][j] = id;
        }
    }
    lcnt = id;
    id = 0;
    for (int j = 1; j <= m; j++) {
        id++;
        for (int i = 1; i <= n; i++) {
            if (arr[i][j] == '#') {
                id++;
                continue;
            }
            r[i][j] = id;
        }
    }
    rcnt = id;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == '*') {
                adj[l[i][j]].push_back(r[i][j]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= lcnt; i++) {
        vis_id++;
        ans += dfs(i);
    }
    cout << ans << endl;
}