本期主要内容：二分图（染色法判定二分图，二分图的最大匹配、多重匹配、带权匹配；二分图最大独立集、最小点覆盖、最大团；二分图的最大匹配边与可行边，有向无环图的最小路径覆盖）；网络流初步（最大流、最小割、最大流最小割定理，EK, Dinic, ISAP 算法）。
二分图
定义什么的我就不写了，不然的话补到明年都补不完了……
染色法判断二分图
依据二分图的定义和下面的定理：
一张无向图是二分图，当且仅当图中不存在长度为奇数的环。
因为如果存在长度为奇数的环，说明不能将图中的结点分成不相交的两部分。根据此定理可以使用染色法用来进行二分图的判定——将每个结点设置一个状态，0表示未染色，1表示白色，2表示黑色；对所有未染色的点进行 DFS，并将该点所能达到的其它点染上与之相反的颜色。如果在上述过程中发现了颜色重涂，说明该图不是一张二分图。
int vis[MAXN], flag = 1;
void dfs(int x, int cur) {
vis[x] = cur;
for (int i = head[x]; i; i = e[i].next) {
if (vis[e[i].v] == 0)
dfs(vis[e[i].v], 3 - cur); // 注意这里的小技巧，3-1=2, 3-2=1.
else if (vis[e[i].v] == cur) {
flag = 0;
return;
}
}
}
for (int i = 0; i < n; i++) {
if (!vis[i] && flag)
dfs(i, 1);
if (!flag)
break;
}
printf(flag ? "Yes" : "No");
二分图的最大匹配
定义部分的介绍略去，通俗的说就是，对于二分图两部分的结点，你要从两部分中选出最多组相连的结点，当然，一个点只能连一个点。
定义已被匹配的点成为“匹配点”，同理定义“非匹配点”、“匹配边”、“非匹配边”。如果二分图中存在一条连接两个非匹配点的路径 $p$, 使得非匹配边与匹配边在 $p$ 上交替出现，称路径 $p$ 是一条增广路。（画个图，随意设定几个匹配点，然后找一条符合上述要求路径，就能明白了）。因为非匹配边和匹配边必须交替出现，且路径两头连接的是非匹配结点，说明路径的第一条边和最后一条边一定是非匹配边，因此 $p$ 的长度一定是奇数。
定理：二分图的一组匹配 S 是最大匹配，当且仅当图中不存在 S 的增广路。
根据上述的定理我们可以使用匈牙利算法来求解问题，算法的步骤如下：
- 初始化所有的边为非匹配边
- 对二分图左部的点 x 尝试进行匹配：遍历左部结点的每条边，如果通向的右部点 y 未被匹配，则将右部的点 y 与 x 匹配
- 若通向右边的点 y 已被匹配，设右部结点已匹配的点为 t，则首先为 t 匹配一个新的左部点
如果 t 能匹配到左部的结点，那么将 y 与 x 匹配，返回 true（不改变原先答案数的情况下为 x 找到匹配，即找到增广路）；否则返回 false （将 x 匹配不会更新答案，也就是没有找到增广路）
int vis[MAXN], match[MAXN], ans = 0; bool dfs(int x) { for (int i = head[x], y; i ; i = e[i].next) { y = e[i].v; if (!vis[y]) { vis[y] = 1; if (!match[y] || dfs(match[y])) { match[y] = x; return true; } } } return false; } for (int i = 0; i < n; i++) { memset(vis, 0, sizeof vis); // vis 标记点是否在 dfs 栈中 if (dfs(i)) ans++; }
二分图的最大匹配也可以用网络流的最大流模型来求解，具体的建图方法为：虚拟出两个节点 s, t，将 s 与所有左部结点连一条流量上限为 1 的边，将 t 与所有右部结点连一条流量上限为 1 的边，然后左右部结点之间保持原先的连边关系，每条边的容量设为 1，建完图跑最大流即可。那么为什么要用网络流来解二分图最大匹配呢，因为匈牙利算法（增广路算法）的时间复杂度是 $O(NM)$ 的，数据规模很大的时候是做不了的，但是我们可以引入最大流模型从而使用 Dinic 等算法解题。使用 Dinic 跑二分图最大匹配的复杂度是 $O(m\sqrt{n})$ 的，比匈牙利快到不知道哪里去了。但是鉴于匈牙利算法的编码难度较低，所以在数据规模较小的时候还是可以用该算法的。
在构建二分图匹配模型的时候，我们需要确认模型中存在“0要素”和“1要素”：0要素要求二分图中的结点能分成两个独立的几何，并且每个集合内部有 0 条边；1要素要求每个结点只能与 1 条匹配边相连。
二分图的完备匹配：如果二分图的左右两部分结点数量均为 $n$，且最大匹配包含 $n$ 重匹配边，则该二分图具有完备匹配。
二分图多重匹配
在二分图最大匹配的基础上，将每个左部的点只能匹配一个右部的点的限制改为：每个左部的点 $i$ 最多可以匹配 $k_i$ 个右部的点，每个右部的点 $j$ 最多可以匹配 $k_j$ 个左部的点。这样的问题一般有以下解决方案：
- 拆点，将左部第 $i$ 个点拆成 $k_i$ 个结点，右边的点拆成 $k_j$ 个结点。拆点后节点间的连接关系也要复制，然后求解二分图最大匹配。
- 如果 $k_j = 1$，那么可以对左部结点跑匈牙利算法的时候跑 $k_i$ 次 DFS；若 $k_i = 1$ 则为右部结点跑匈牙利算法，一个结点跑 $k_j$ 次 DFS。
- 网络流模型。设置虚拟的源点 s 和汇点 t，将所有的左部结点 $i$ 到 s 连一条流量为 $k_i$ 的边，将所有的右部结点 $j$ 到 t 连一条流量为 $k_j$ 的边，中间左部结点和右部结点间的边容量设置为 1，建完图跑最大流。
例题：圆桌问题
建图的思路：首先源点到各个单位连一条容量为 r[i] 的边，然后每个代表到每个桌子都连一条容量为 1 的边，最后每个桌子到汇点连一条容量为 cap[i] 的边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXM = 160, MAXN = 270;
const int INF = 0x3f3f3f3f;
int n, m, rep[MAXM], cap[MAXN];
struct Edge {
int u, v, c, next;
};
struct Dinic {
Edge e[MAXN * MAXN];
int head[MAXN << 1], d[MAXN << 1], cnt, s, t;
queue<int> q;
Dinic(int ts, int tt): s(ts), t(tt) {
memset(head, 0, sizeof head);
memset(e, 0, sizeof e);
cnt = 2;
}
void add_edge(int u, int v, int c) {
e[cnt] = (Edge) { u, v, c, head[u] };
head[u] = cnt++;
e[cnt] = (Edge) { v, u, 0, head[v] };
head[v] = cnt++;
}
bool bfs() {
while (q.size())
q.pop();
memset(d, 0, sizeof d);
q.push(s);
d[s] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = head[cur]; i; i = e[i].next) {
if (e[i].c && !d[e[i].v]) {
d[e[i].v] = d[cur] + 1;
q.push(e[i].v);
if (e[i].v == t)
return true;
}
}
}
return false;
}
int dinic(int x, int flow) {
if (x == t)
return flow;
int rest = flow, k;
for (int i = head[x]; i && rest; i = e[i].next) {
if (e[i].c && d[e[i].v] == d[x] + 1) {
k = dinic(e[i].v, min(rest, e[i].c));
if (!k)
d[e[i].v] = 0;
e[i].c -= k, e[i ^ 1].c += k;
rest -= k;
}
}
return flow - rest;
}
int solve() {
int maxflow = 0, flow = 0;
while (bfs())
while ((flow = dinic(s, INF)))
maxflow += flow;
return maxflow;
}
};
int main() {
scanf("%d%d", &m, &n);
int sum = 0;
for (int i = 0; i < m; i++) {
scanf("%d", &rep[i]);
sum += rep[i];
}
for (int i = 0; i < n; i++) {
scanf("%d", &cap[i]);
}
int s = n + m, t = n + m + 1;
Dinic ek = Dinic(s, t);
for (int i = 0; i < m; i++) {
ek.add_edge(s, i, rep[i]);
for (int j = 0; j < n; j++) {
ek.add_edge(i, m + j, 1);
}
}
for (int i = 0; i < n; i++)
ek.add_edge(m + i, t, cap[i]);
int ans = ek.solve();
if (ans == sum)
printf("1\n");
else {
printf("0");
return 0;
}
for (int i = 0; i < m; i++) {
vector<int> v;
int size = 0;
for (int j = ek.head[i]; j; j = ek.e[j].next) {
if (ek.e[j].c == 0 && ek.e[j].v != s) {
v.push_back(ek.e[j].v - m + 1);
size++;
}
}
for (int j = size - 1; j >= 0; j--)
printf("%d ", v[j]);
printf("\n");
}
return 0;
}
二分图的带权最大匹配
二分图的带权最大匹配：给定一张二分图，二分图的每条边都带有一个权值，求出该二分图的一组最大匹配，使得匹配边的权值总和最大。注意“权值总和最大”的前提是：当前匹配是二分图的最大匹配。
首先是解决这个问题的一个 $O(n^3)$ 算法——KM 算法，该算法只能在满足：带权最大匹配一定是完备匹配的条件下求解。来看几个定义：
交错树：在匈牙利算法中，如果从某个左部结点出发寻找匹配失败，那么在 DFS 的过程中，所有访问过的结点和访问这些节点所构成的边，构成一棵交错树（因为这棵树的根、叶子都是左部结点，并且左右交错）。
顶点标记值：在二分图中，给第 $i$ 个左部结点一个整数值 $A_i$ 和第 $j$ 个右部结点一个整数值 $B_j$，使其满足 $\forall i, j, A_i + B_j \ge w(i, j)$，其中 $w(i, j)$ 是连接结点 $i, j$ 的边的边权（若 $i,j$ 不连通则 $w(i,j) = -\infty$），称 $A_i$ 和 $B_j$ 为节点 $i, j$ 的顶点标记值。
相等子图：二分图中所有节点和满足 $A_i + B_j = w(i, j)$ 的边构成的子图，称为二分图的相等子图。
于是 KM 算法引入了这样一个定理：
在相等子图中如果存在完备匹配，则这个完备匹配一定是二分图的最大匹配。
在相等子图中完备匹配的边权之和为 \Sigma_{i=1}^{n}(A_i+B_j)，也就是所有顶点标记值的和。根据定义顶点标记值之和不会超过边权，所以在整个二分图中，任何一组匹配的边权之和都不可能大于所有顶点标记值的和。
基于上述定理，KM 算法的基本思想就是：首先将每个左部结点的顶点标记值 $A_i$ 设置为经过$i$ 的每条边的最大权值 $max{w(i, j)}$，将每个右部结点的顶点标记值 $B_j$ 设置为 $0$.