定义
对于一个无向图 \(G=(V,E)\),如果存在点集 \(A,B\),满足 \(a\neq\varnothing\),\(b\neq\varnothing\),\(A\cap B=\varnothing\),\(A\cup B=V\),且 \(\forall u,v\in A\) 或 \(u,v\in B\),都有 \((u,v)\notin E\),则称这个图是一个二分图,\(A\) 称为这个二分图的左部,\(B\) 称为右部。
一个二分图可以记作 \(G=(A,B,E)\),下文中使用这种记法时,默认 \(|A|\le|B|\)。
判定
一个图是二分图 \(\iff\) 图中没有奇环。
可以用 DFS 染色 或 扩展域并查集 判断。
例题:
二分图最大匹配
定义
-
对于一个图 \(G=(V,E)\),如果一个边集 \(S\subseteq E\) 满足其中任意两条不同的边没有公共端点,则称 \(S\) 为图 \(G\) 的一个匹配。
-
对于匹配 \(S\),属于 \(S\) 的边叫做匹配边,不属于 \(S\) 的边叫做非匹配边。
-
如果点 \(u\) 是一条匹配边的端点,则称 \(u\) 为匹配点,否则是非匹配点。
匹配边的两端都是匹配点;非匹配边的两端要么都是匹配点,要么一个是匹配点,一个是非匹配点。
-
对于二分图 \(G=(A,B,E)\),如果它的一个匹配 \(S\) 满足 \(A\) 中所有点都是匹配点,则称 \(S\) 为 \(G\) 的一个完美匹配。
求解
二分图最大匹配问题可以用网络流求解。建立超级源点 \(S\) 和超级汇点 \(T\),原图中每条边从左部连向右部,容量为 \(1\),从 \(S\) 向每个左部点连一条容量为 \(1\) 的边,从每个右部点向 \(T\) 连一条容量为 \(1\) 的边,新图的最大流就是最大匹配,其中匹配边流量为 \(1\),非匹配边流量为 \(0\)。
在单位容量的网络中,使用 Dinic 的时间复杂度为 \(O(m\sqrt n)\)。
我太菜了,不会匈牙利算法。
模板代码:(Luogu P3386 【模板】二分图最大匹配)
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
// #define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 1005, M = 2e5 + 5;
int n, m, e, t;
int hd[N], to[M], nxt[M], cap[M], tot = 1;
int dep[N], cur[N];
void add(int u, int v, int w) {
to[++tot] = v;
cap[tot] = w;
nxt[tot] = hd[u];
hd[u] = tot;
}
bool bfs() {
memset(dep, 0, sizeof dep);
queue<int> q;
q.push(0);
dep[0] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = hd[u]; i; i = nxt[i])
if(cap[i] && !dep[to[i]])
dep[to[i]] = dep[u] + 1, q.push(to[i]);
}
return dep[t];
}
int dfs(int u, int flow) {
if(u == t) return flow;
int res = 0;
for(int i = cur[u]; i && flow; i = nxt[i]) {
cur[u] = i;
if(dep[to[i]] == dep[u] + 1) {
int o = dfs(to[i], min(cap[i], flow));
flow -= o;
res += o;
cap[i] -= o;
cap[i ^ 1] += o;
}
}
return res;
}
int dinic() {
int ans = 0;
while(bfs()) {
rep(i, 0, t) cur[i] = hd[i];
ans += dfs(0, INT_MAX);
}
return ans;
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> m >> e;
t = n + m + 1;
rep(i, 1, e) {
int u, v; cin >> u >> v;
v += n;
add(u, v, 1), add(v, u, 0);
}
rep(i, 1, n) add(0, i, 1), add(i, 0, 0);
rep(i, 1, m) add(i + n, t, 1), add(t, i + n, 0);
cout << dinic() << endl;
return 0;
}
常见模型
最小路径覆盖
对于一个有向无环图 \(G=(V,E)\),如果存在一个简单路径的集合 \(S\),满足 \(V\) 中的每个点都恰好在 \(S\) 中的一条路径上,则称 \(S\) 为 \(G\) 的一个路径覆盖。求出所含路径条数最少的路径覆盖。
首先每个点单独构成一条路径肯定是一组路径覆盖。考虑通过图中的边合并这些路径使它变小。
将每个点 \(u\) 拆成两个点 \(u_{in}\) 和 \(u_{out}\),对于原图中的每一条边 \((u,v)\),在新图中连接 \((u_{out},v_{in})\)。在路径覆盖中,每个点最多只有 \(1\) 条入边和 \(1\) 条出边,这对应着新图中的每个点最多只被一条边选中,因此求出新图的最大匹配 \(P\),每选择一条边代表合并了一次路径,最小路径覆盖的大小即为 \(|V|-P\)。每条匹配边对应路径覆盖中的一条边,因此也容易构造出最小路径覆盖。
代码:(Luogu P2764 最小路径覆盖问题)
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
// #define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 205, M = 6005;
int n, m, t;
int to[M * 4], nxt[M * 4], cap[M * 4], hd[N * 2], tot = 1;
int cur[N * 2], dep[N * 2];
int fr[N];
void add(int u, int v, int w) {
to[++tot] = v;
cap[tot] = w;
nxt[tot] = hd[u];
hd[u] = tot;
}
bool bfs() {
memset(dep, 0, sizeof dep);
dep[0] = 1;
queue<int> q;
q.push(0);
while(!q.empty()) {
int u = q.front();
cur[u] = hd[u];
q.pop();
for(int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if(cap[i] && !dep[v])
dep[v] = dep[u] + 1, q.push(v);
}
}
return dep[t];
}
int dfs(int u, int flow) {
if(u == t) return flow;
int res = 0;
for(int i = cur[u]; i && flow; i = nxt[i]) {
cur[u] = i;
int v = to[i];
if(dep[v] == dep[u] + 1) {
int o = dfs(v, min(flow, cap[i]));
flow -= o;
res += o;
cap[i] -= o;
cap[i ^ 1] += o;
}
}
return res;
}
int dinic() {
int ans = 0;
while(bfs()) ans += dfs(0, INT_MAX);
return ans;
}
int find(int x) {
for(int i = hd[x]; i; i = nxt[i])
if(!(i & 1) && !cap[i]) return to[i] - n;
return 0;
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> m;
t = n * 2 + 1;
rep(i, 1, n) {
add(0, i, 1), add(i, 0, 0);
add(i + n, t, 1), add(t, i + n, 0);
}
rep(i, 1, m) {
int u, v; cin >> u >> v;
add(u, v + n, 1), add(v + n, u, 0);
}
int ans = n - dinic();
rep(i, 1, n) fr[find(i)] = i;
rep(i, 1, n) if(!fr[i]) {
cout << i << ' ';
int o = find(i);
while(o) {
cout << o << ' ';
o = find(o);
}
cout << endl;
}
cout << ans << endl;
return 0;
}
最小可重路径覆盖
对于一个有向无环图 \(G=(V,E)\),如果存在一个简单路径的集合 \(S\),满足 \(V\) 中的每个点都至少在 \(S\) 中的一条路径上,则称 \(S\) 为 \(G\) 的一个可重路径覆盖。
做传递闭包后转化为不可重路径覆盖。
常用定理
König 定理
对于二分图 \(G=(V,E)\),设 \(P\) 为其最大匹配的大小,则有最小点覆盖 \(=P\)(点覆盖:一个点集 \(S\subseteq V\),满足 \(\forall(u,v)\in E\),都有 \(u\in S\lor v\in S\)。即每条边至少选择一个端点)
-
证明(含构造方案):
-
首先显然有最小点覆盖 \(\ge P\),因为每条匹配边至少有一个端点被选择。
-
考虑从右部每个非匹配点开始 DFS,从右往左只能走非匹配边,从左往右只能走匹配边。设 左部被 DFS 到的点 和 右部没被 DFS 到的点 构成的集合为 \(S\),\(S\) 就是一个最小点覆盖。
-
首先证明 \(|S|=P\):
-
首先注意到每次 DFS 中,除了起点,被 DFS 到的都是匹配点。
-
因为从左往右只能走匹配边,也就只能走到匹配点。而从右往左虽然只能走非匹配边,但是走不到非匹配点,因为如果走到了非匹配点,就说明发生了以下这种情况:(红色为匹配边)
-
显然这存在更大的匹配,与最大匹配矛盾,因此不可能从右部走到非匹配点。
-
而右部的非匹配点都作为起点被 DFS 过,没被 DFS 过的只能是匹配点。如果右部的一个匹配点没被 DFS 过,它就会被加入 \(S\)。右部的一个匹配点被 DFS 过,当且仅当其对应的左部匹配点也被 DFS 过,因此这个左部匹配点被加入 \(S\)。这说明对于每条匹配边,都有且仅有一个端点被加入了 \(\boldsymbol S\)。因此 \(|S|=P\)。
-
-
然后证明 \(S\) 是一个点覆盖:
- 上文已经证明匹配边肯定全被覆盖。一条非匹配边没被 \(S\) 覆盖到的充要条件是,左部端点没被 DFS 过 且 右部端点被 DFS 过。
- 如果一个右部点被 DFS 过,则所有与它相连的非匹配边都被 DFS 过,因此这个条件不可能满足,即不存在未被覆盖的边,所以 \(S\) 是一个点覆盖。
-
综上,\(S\) 是一个最小点覆盖。
-
推论:最大独立集 \(=|V|-P\)(独立集:一个点集 \(S\subseteq V\),满足 \(\forall u,v\in S\),都有 \((u,v)\notin E\)。即选择的点之间不能有边)
-
证明:
- 对于每个独立集 \(S\),其补集 \(\complement_VS\) 都是一个点覆盖。
- 所以最大独立集对应最小点覆盖,大小为 \(|V|-P\)。
最小边覆盖
对于二分图 \(G=(V,E)\),设 \(P\) 为其最大匹配的大小,则有最小边覆盖 \(=|V|-P\)(边覆盖:一个边集 \(S\subseteq E\),满足 \(\forall u\in V\),都 \(\exists v\in V,(u,v)\in E\)。即每个点至少选择一条出边)
-
证明:
- 一条边加入边覆盖中,可能覆盖了一个或两个未覆盖的点。
- 要使边覆盖最小,就要让覆盖了两个未覆盖点的边最多。
- 这种边就是匹配边,向边覆盖中加入每条匹配边,总共覆盖了 \(2P\) 个点。
- 剩下的点每个点对应一条边,这些边的数量为 \(|V|-2P\),边覆盖中的总边数就是 \(|V|-2P+P=|V|-P\)。
Hall 定理:
对于二分图 \(G=(A,B,E)\),定义函数 \(f(S)\) \((S\subseteq A)\) 表示与 \(S\) 中的点有连边的点的数量,则 \(G\) 存在完美匹配的充要条件是 \(\forall S\subseteq A,f(S)\ge|S|\)。
看着很对,证明不会。
Dilworth 定理
对于一个有向无环图 \(G=(V,E)\),其最长反链的大小等于最小可重路径覆盖的大小。
反链:如果一个点集 \(S\subseteq V\) 满足 \(\forall u,v\in S,u\neq v\),不存在 \(u\) 到 \(v\) 的路径,则称 \(S\) 为图 \(G\) 的一个反链。
证明不会。
模板题:Luogu P4298 [CTSC2008] 祭祀
给定一个有向无环图 \(G=(V,E)\, (|V|=n,|E|=m)\),有三问:
- 求出其最长反链长度。
- 构造最长反链。
- 判断每个点是否可能在最长反链中。
\(n\le100,m\le1000\)。
第一问,根据 Dilworth 定理,做出传递闭包,做最小不可重路径覆盖即可。构造的二分图 \(G'=(V_{in},V_{out},E')\) 中的一条边 \((u_{out},v_{in})\in E\) 代表 \(u\) 能到达 \(v\)。
第二问,找出二分图的最大独立集 \(S\),所有满足 \(u_{in}\in S\land u_{out}\in S\) 的 \(u\) 构成的集合 \(L\) 就是最长反链。最大独立集是最小点覆盖的补集,先求出最小点覆盖再求补集即可,构造方案见上文 König 定理。
因为取出的每个 \(u\) 都满足 \((u_{in},u_{out})\) 都在同一个独立集中,所以这些点也构成独立集,也就是不存在边 \((u_{in},v_{out})\)(代表 \(u\) 能到达 \(v\)),满足反链的定义。
接下来证明这些点构成的反链是最长的:
设 \(P\) 是 \(G'\) 的最大匹配数,显然 \(P\le n\),\(|S|=|V_{in}|+|V_{out}|-P=2n-P\)。满足在 \(v_{in}\) 和 \(v_{out}\) 中有且仅有一个属于 \(S\) 的节点 \(v\) 最多只有 \(n-|L|\) 个,而每个 \(L\) 中的元素在 \(S\) 中对应两个元素,所以 \(|S|-2|L|\) 就是这样的 \(v\) 的数量,所以 \(|S|-2|L|\le n-|L|\),移项得到 \(|L|\ge|S|-n\) 即 \(|L|\ge n-P\),反链最长也只有 \(n-P\),所以 \(|L|=n-P\),\(L\) 是最长反链。
第三问,枚举每个点分别判断。考虑强制选中这个点,然后再求最长反链,如果最长反链不变,这个点就可以在最长反链中。具体地,如果选中一个点,那么所有和这个点有偏序关系(路径)的点都不能选,所以将这些点都删掉,对剩下的点求最长反链,如果只减少了 \(1\),这个点就合法。
时间复杂度:求传递闭包的时间复杂度为 \(O(n^3)\),求完传递闭包后的边数 \(m'=O(n^2)\),跑一次二分图匹配的时间复杂度是 \(O(m'\sqrt n)=O(n^{2.5})\),第三问要枚举每个点分别跑二分图匹配,所以总时间复杂度为 \(O(n^{3.5})\)。
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
// #define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 105, M = 1005;
int n, m, c[N][N];
int to[N * N], nxt[N * N], cap[N * N], hd[N * 2], tot = 1;
int cur[N * 2], dep[N * 2], t;
bool del[N * 2], vis[N * 2];
string s1, s2;
void add(int u, int v, int w) {
to[++tot] = v;
cap[tot] = w;
nxt[tot] = hd[u];
hd[u] = tot;
}
bool bfs() {
memset(dep, 0, sizeof dep);
dep[0] = 1;
queue<int> q;
q.emplace(0);
while(!q.empty()) {
int u = q.front();
q.pop();
cur[u] = hd[u];
for(int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if(cap[i] && !del[v] && !dep[v]) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u, int flow) {
if(u == t || !flow) return flow;
int res = 0;
for(int i = cur[u]; i && flow; i = nxt[i]) {
cur[u] = i;
int v = to[i];
if(!del[v] && dep[v] == dep[u] + 1) {
int o = dfs(v, min(cap[i], flow));
flow -= o;
res += o;
cap[i] -= o;
cap[i ^ 1] += o;
}
}
return res;
}
int dinic() {
int ans = 0;
while(bfs()) ans += dfs(0, n);
return ans;
}
void recover() {
rep(i, 2, tot)
if(i & 1) cap[i] = 0;
else cap[i] = 1;
memset(del, 0, sizeof del);
}
void dfs(int u) {
vis[u] = 1;
for(int i = hd[u]; i; i = nxt[i])
if(!vis[to[i]] && !cap[i]) dfs(to[i]);
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> m;
rep(i, 1, m) {
int u, v; cin >> u >> v;
c[u][v] = 1;
}
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n)
c[i][j] |= c[i][k] & c[k][j];
t = n * 2 + 1;
rep(i, 1, n) rep(j, 1, n)
if(c[i][j]) add(i, j + n, 1), add(j + n, i, 0);
rep(i, 1, n)
add(0, i, 1), add(i, 0, 0), add(i + n, t, 1), add(t, i + n, 0);
int l = n - dinic();
cout << l << endl;
vis[0] = vis[t] = 1;
for(int i = hd[t]; i; i = nxt[i])
if(!cap[i]) dfs(to[i]);
rep(i, 1, n) s1.push_back(!vis[i] && vis[i + n] ? '1' : '0');
cout << s1 << endl;
rep(i, 1, n) {
recover();
del[i] = del[i + n] = 1;
int t = n - 1;
rep(j, 1, n) if(c[i][j] | c[j][i]) del[j] = del[j + n] = 1, --t;
s2.push_back(t - dinic() == l - 1 ? '1' : '0');
}
cout << s2 << endl;
return 0;
}
缝合题:CF590E Birthday
标签:二分,匹配,int,cap,笔记,学习,dep,add,define From: https://www.cnblogs.com/untitled0/p/bipartite-graph.html给定 \(n\) 个仅包含 \(\texttt{a,b}\) 的字符串,保证它们两两不同。
你需要留下尽可能多的字符串,使得这些字符串中不存在某一个串是另一个串的子串,输出方案。
\(n\le750,\sum_{i=1}^n|s_i|\le10^{7}\)。