\(\text{Thanks for wikipedia}\)
二分图的顶点可分成 两互斥的独立集 \(U\) 和 \(V\) , 使得所有边都连结一个 \(U\) 中的点和一个 \(V\) 中的点 .
顶点集 \(U, V\) 被称为是图的两个部分.
等价的 , 二分图 可以被定义成 图中所有的环都有偶数个顶点 .
\[\text{图 1}\]
如图 \(1\) , 可将\(U\) 和\(V\) 当做一个着色 :
\(U\) 中所有顶点为蓝色 , \(V\) 中所有顶点着绿色 , 每条边的两个端点的颜色不同, 符合图着色问题的要求 .
\[\text{图 2}\]
相反的 , 非二分图无法被二着色 ,
如图 \(2\) , 将其中一顶点着蓝色 且另一着绿色后 , 第三个顶点 与上述具有两颜色的顶点相连 , 无法再对它着蓝色或绿色 .
给定一张图 G , 在 G的一子图 M 中 , M 的边集中的任意两条边都没有共同的端点 , 则称 M是一个匹配
对于图 \(1\) 所示二分图 , 图 \(3\) 的选择方案 , 即为 图 \(1\)的一匹配
\[\text{图 3}\]
给定一张图 \(G\) , 其中边数最多的匹配 , 即该图的最大匹配
对于图 \(1\) 所示二分图 , 图 \(4\) 的选择方案 , 即为 图 \(1\)的一最大匹配
\[\text{图 4}\]
最大匹配可能不唯一 , 但最大匹配的边数确定 , 且不可能超过图中顶点 数的一半 .
根据匹配的性质 , 一匹配中 不同边对应的两对顶点 完全不同 , 否则它们相邻 , 不满足匹配的定义
最小顶点覆盖要求用最少的点 , 让每条边都至少和其中一个点关联 .
\(\text{Knoig}\) 定理 : 二分图的最小顶点覆盖数等于二分图的最大匹配数 .
在 \(n\) 个点的图 \(G\) 中选出 \(m\) 个点 , 使这 \(m\) 个点两两之间没有连边 , 求\(m\) 最大值 .
引理 : 二分图的最大独立集数 = 节点数(\(n\)) — 最大匹配数(\(m\))
模板题 : https://vjudge.net/problem/HihoCoder-1121
通过 二分图可被二着色的性质可得 ,
一个无向图是否为 二分图 , 可通过 \(dfs / bfs\) 染色 , 来进行判断 .
对于图中每一联通块 , 任选其中一点 , 将其染为绿色
显然 , 为满足每一条边两端点颜色都不同 , 与选择点相连的点 都应被染为蓝色
则可使用 \(bfs\)进行模拟染色 :
\(dfs\) 与 \(bfs\) 的复杂度 都为\(O(n)\) , 为避免出现递归爆栈情况 , 一般使用 \(bfs\)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_V = 205;
vector<int> G[MAX_V]; // 图
int V; // 顶点数
int color[MAX_V]; // 顶点i的颜色 1 或 -1
// 把顶点染成1或-1
bool dfs(int v, int c)
{
color[v] = c; // 把顶点v染成颜色c
for (int i = 0; i < G[v].size(); ++i) {
if (color[G[v][i]] == c) return false;
if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
}
return true;
}
void solve()
{
for (int i = 0; i < V; ++i) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
puts("Wrong\n");
return ;
}
}
}
puts("Correct\n");
}
int main()
{
int E;
while (scanf("%d%d", &V, &E) == 2) {
int a, b;
for (int i = 0; i < V; ++i) G[i].clear();
memset(color, 0, sizeof color);
for (int i = 0; i < E; ++i) {
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
solve();
}
return 0;
}//By:Luckyblock
#include <cstdio>
#include <cstring>
#include <queue>
#include <ctype.h>
const int MARX = 1e4 + 10;
//=============================================================
struct edge
{
int u, v, ne;
}e[MARX << 3];
int num, T, N, M, head[MARX], color[MARX];
//=============================================================
inline int read()
{
int s = 1, w = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
return s * w;
}
inline void add(int u, int v)
{
e[++ num].v = v, e[num].u = u;
e[num].ne = head[u], head[u] = num;
}
bool bfs()
{
for(int i = 1; i <= N; i ++)
if(head[i] && color[i] == 0)//找到未被染色的 联通块
{
std :: queue <int> q;
while (!q.empty()) q.pop();
q.push(i); color[i] = 1;//对起点 进行染色
while(! q.empty())
{
int u = q.front(); q.pop();
for(int j = head[u]; j; j = e[j].ne)
{
int v = e[j].v;
if(color[v] == color[u]) return 0;//一边两端点 颜色相同 , 则不合法
if(! color[v]) color[v] = - color[u], q.push(v);// 染为相反色
}
}
}
return 1;
}
//=============================================================
signed main()
{
T = read();
while(T --)
{
num = 0;
memset(head, 0, sizeof(head));
memset(color, 0, sizeof(color));
N = read(), M = read();
bool flag = 1;
for(int i = 1; i <= M; i ++)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
if(bfs()) printf("Correct\n");
else printf("Wrong\n");
}
}算法核心
对于一匹配 \(M\) ,
增广路径是指从 \(M\) 中未使用的顶点开始 , 并从 \(M\) 中未使用的顶点结束的交替路径 .
可以证明 , 一个匹配是最大匹配 , 当且仅当它没有任何增广路经
匈牙利算法的核心 即寻找增广路径 , 它是一种用增广路径 求 二分图最大匹配的算法
算法流程 :
先将给定二分图分为 \(U\) , \(V\) 两独立集 , 枚举 \(U\) 中结点
对当前枚举\(U\) 中结点 \(u\), 枚举其相邻 的\(V\) 中结点 \(v\)否则 , 枚举 \(v\) 相邻的 \(U\)中结点 , 递归检查 \(v\) 点的匹配点 是否可与其他 \(V\)中结点 配对 .
若可以 , 则 \(u\) 可与 \(v\) 点进行匹配 , 加入最大匹配中
否则 , \(u\) 不可与 \(v\) 匹配 , \(u\) 点无匹配点 , 不可加入最大匹配中
手动模拟 :
写的太垃圾看不懂 ? 手玩一组数据试试 :
\[\text{图 5}\]
对 Yugari 进行匹配 :
其直接连接点 Reimu 未被匹配 , 则将 Yugari 与 Reimu 进行匹配
对 Marisa 进行匹配 :
其直接连接点 Patchouli 未被匹配 , 则将 Marisa 与 Patchouli 进行匹配
对 Aya 进行匹配 :
其直接连接点 Reimu 被匹配 , 检查 Reimu 的匹配点 Suika 能否寻找到其他匹配点由于Suika 匹配对象不可改变 , Reimu 被匹配 , 则 Aya 无匹配点
则此二分图的一种最大匹配为 :
\[\text{图 6}\]
例题 :
模板题
//By:Luckyblock
#include <cstdio>
#include <cstring>
#include <ctype.h>
#define ll long long
const int MARX = 1e3 + 10;
const int MARX1 = 1e7 + 10;
//=============================================================
struct edge
{
int u, v, ne;
}e[MARX1];
int N, M, E, num, ans, head[MARX], match[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
int s = 1, w = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
return s * w;
}
void add(int u, int v)
{
e[++ num].u = u, e[num].v = v;
e[num].ne = head[u], head[u] = num;
}
bool dfs(int u)//匈牙利算法配对
{
for(int i = head[u]; i; i = e[i].ne)//枚举能到达的点
if(! vis[e[i].v])//在此轮配对中未被访问
{
vis[e[i].v] = 1;
if(! match[e[i].v] || dfs(match[e[i].v]))//若可配对
{
match[e[i].v] = u;//更新
return 1;
}
}
return 0;
}
//=============================================================
signed main()
{
N = read(), M = read(), E = read();
for(int i = 1; i <= E; i ++)
{
int u = read(), v = read();
if(u > N || v > M) continue;
add(u, v);
}
for(int i = 1; i <= N; i ++)//枚举一组中的N个点
{
memset(vis, 0, sizeof(vis));//初始化
if(dfs(i)) ans ++;//可以将i点 加入匹配中
}
printf("%d", ans);
}二分图匹配 模板 , 使用匈牙利算法
题目要求输出方案
显然 , 没有匹配对象的点 , 其匹配对象为 0
将匹配完成后 各点的非0匹配对象输出即可
//By:Luckyblock
#include <cstdio>
#include <cstring>
#include <ctype.h>
#define ll long long
const int MARX = 1e3 + 10;
const int MARX1 = 1e7 + 10;
//=============================================================
struct edge
{
int u, v, ne;
}e[MARX1];
int N, M, E, num, ans, head[MARX], match[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
int s = 1, w = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
return s * w;
}
void add(int u, int v)
{
e[++ num].u = u, e[num].v = v;
e[num].ne = head[u], head[u] = num;
}
bool dfs(int u)//匈牙利算法配对
{
for(int i = head[u]; i; i = e[i].ne)//枚举能到达的点
if(! vis[e[i].v])//在此轮配对中未被访问
{
vis[e[i].v] = 1;
if(! match[e[i].v] || dfs(match[e[i].v]))//若可配对
{
match[e[i].v] = u; //更新
return 1;
}
}
return 0;
}
//=============================================================
signed main()
{
N = read(), M = read();
while(1)
{
int u = read(), v = read();
if(u == -1 && v == -1) break;
add(u, v);
}
for(int i = 1; i <= N; i ++)//枚举一组中的N个点
{
memset(vis, 0, sizeof(vis));//初始化
if(dfs(i)) ans ++;//可以将i点 加入匹配中
}
printf("%d\n", ans);
for(int i = N + 1; i <= M; i ++)//输出方案
if(match[i]) printf("%d %d\n", match[i], i);
}咕了咕了 要是没退役就再来更吧 = =
原文：https://www.cnblogs.com/luckyblock/p/11808985.html