首页 > 其他分享 >归档 230502 // 二分图

归档 230502 // 二分图

时间：2023-05-09 20:56:19浏览次数：62  
标签：二分 匹配 增广 int 230502 maxn 归档 return

So why not 二分图？

二分图

二分图总体概念不难。主要是其应用广泛，需要注意什么样的题目可以联系到二分图上来。

概念

若图 \(G\) 可将点集 \(V\) 分成两个互不相交的子集 \(X\) 和 \(Y\)，且每条边连接的两个点都满足一个在 \(X\) 中，一个在 \(Y\) 中，则称 \(G\) 为二分图。

也就是说，如果一个图有任何一种分组方式满足：把图中的点分成两组，每一组的点两两之间没有连边，那么这个图就是二分图。

举个例子：

每一组中的点两两之间没有连边，所以该图是二分图。

性质

  • 二分图的每条边连接的点属于不同的集合。

    显然。

  • 二分图中可能存在环，且长度一定为偶数。

    我们指定环中任意一个点，从该点出发，易得，经过奇数条边时到达另一个集合，反之回到该集合。因为路径是一个环，所以我们最后一定会回到起点所在集合，即经过偶数条边。

判定

通常，我们使用图的深度优先遍历每一个点 \(u\)。

显然，若已知点 \(u\) 在 \(X\) 集，那么所有与 \(u\) 有连边的点 \(v\) 一定在 \(Y\) 集（反之同理）。

当然，很多图是有环的，不免会产生 \(v\) 已经被分组的情况。若此时 \(v\) 恰好在 \(Y\) 集，皆大欢喜；若 \(v\) 也在 \(X\) 集，那么该图一定不为二分图。

由于每个点最多搜索一次，时间复杂度 \(\mathcal O(n)\)。

int col[maxn];
bool DFS(int x, int c) {
	col[x] = c;
    for (auto i : g[x]) {
        if (col[i]) {
            if (col[i] == c)
                return 0;
        }
        else if (!DFS(i, 3 - c))
            return 0;
    }
    return 1;
}
int main() { DFS(1, 1); }

厚颜无耻地推销一下 题目（（（

匹配

定义：对于一个二分图中的若干条边，若这些边没有任何公共点，则称这些边组成的集合 \(M\) 是数量为 \(|M|\) 的 匹配。

图中红色边展示了一个数量为 4 的匹配

容易看出，对于点 \(u\)，只会存在 「有一条 \(M\) 集合内的边与 \(u\) 相连接」 和 「\(u\) 连接的边均不在 \(M\) 集合内」 两种情况。也就是说，从 \(u\) 出发的 \(M\) 集合内的边，最多有 \(1\) 条。

接下来，我们称 「有任何一条与之相连的边在匹配集合内」 的点为匹配点，「在匹配集合内的边」 为匹配边。

完备匹配

如果 \(|M|=\dfrac n2\)，即 \(M\) 恰好连接了 \(1\sim n\) 所有点，我们就称匹配 \(M\) 为 完备匹配。

一个完备匹配的例子

比方说，现在我们知道一些男孩和女孩，他们之间有若干条互相喜欢的关系，我们把此关系抽象成一个二分图，如果每个人都能与自己喜欢的异性配对，那么我们认为这个关系网存在完备匹配。

显然，完备匹配存在，仅当两集合大小相等。

匈牙利算法

匈牙利算法一般用于求解 \(\max\{|M|\}\)。

我们将图上满足下列条件的路径 \(P\) 称为增广路：

  • \(P\) 的起点和终点均是非匹配点
  • \(P\) 的起点和终点不在二分图的同一组内
  • 路径 \(P\) 经过的边按 非 匹配边，匹配边，\(\cdots\)，非 匹配边的规律交替。

最终，\(P\) 会呈类 「\(\text Z\)」 形（值得一提的是，增广路不能经过一整个环，否则其长度将会因为二分图中只存在偶环而变为无穷大）。

显然，非匹配边比匹配边的数量始终多 \(1\)。

此时，我们对 \(P\) 上匹配的状态取反。也就是说，原来的非匹配边变成匹配边，匹配边变成非匹配边。这样做相当于是在匹配边集仍然合法的情况下将匹配边集的大小扩大了 \(1\)。

那么增广路经过的边按非匹配边，匹配边，\(\cdots\)，非匹配边顺序交替的原因就很显而易见了。取反前，匹配边不可能连续出现；取反后，匹配边（即取反前的非匹配边）也不可能连续出现。

而匈牙利算法的主要思路，就是反复寻找增广路，直到无法找到为止。

这里就必须再提到一个性质：\(M\) 为图 \(G\) 的最大匹配，当且仅当无法在 \(M\) 的基础上找到增广路。

证明如下：

  • 有引理：对于图 \(G\) 的任意两个匹配 \(M\) 和 \(M'\)，它们的 对称差 \(M\Delta M'\) 中的每一个连通块都是一条链或一个包含边数为偶数的环。

    证明：

    根据对称差的定义，对于任意边 \(e\in M\Delta M'\)，\(e\) 要么是 \(M\) 中的一条匹配边，要么是 \(M'\) 中的一条匹配边，但不同时被 \(M\) 和 \(M'\) 包含。

    因为在同一个匹配中，任意两条匹配边不存在公共顶点，所以对于任意与 \(e\) 有公共顶点的匹配边 \(e'\)，\(e\) 和 \(e'\) 必然来自两个不同的匹配。

    由此可得，对于任意匹配点 \(u\)，\(u\) 的度数为 \(1\) 或 \(2\)。

    所以，对称差中的每一个连通块都是链或环。

    对于其中的环，所有相邻的边必定来自不同的匹配，所以环包含的边数为偶数。

  • 必要性：当 \(M\) 为最大匹配时，无法找到 \(M\) 的增广路。

    我们已经知道了，找到某匹配的增广路 \(P\) 并将其匹配状态取反，可以使匹配大小加一。

    如果 \(M\) 存在增广路，则我们可以将其取反，得到一个比 \(M\) 大小更大的匹配。与 \(M\) 是最大匹配矛盾。

    所以一定不存在 \(M\) 的增广路。

  • 充分性：如果不存在 \(M\) 的增广路，\(M\) 为 \(G\) 的最大匹配。

    设 \(M'\) 是一个比 \(M\) 更大的匹配。

    由引理得：

    在它们的对称差 \(M\Delta M'\) 中，连通块为链或环。

    其中，环包含边的数量为偶数，所以必然有同样多的边来自 \(M\) 和 \(M'\)。所以我们可以忽视这些环。

    由于 \(|M|<|M'|\)，存在至少一条链 \(L\)，且 \(|L|=k-1\)，包含 \(k\) 条 \(M\) 中的边，\(k+1\) 条来自于 \(M'\) 的边。

    显然，\(L\) 就是一条 \(M\) 的增广路，所以我们必然可以找到一条 \(M\) 的增广路，命题成立。

对于 「寻找增广路」 这个过程，我们使用 DFS 算法实现。

对于点 \(x\)，若与 \(x\) 有连边的点 \(y\) 可匹配上 \(x\)，需要满足下列两个条件之一：

  • \(y\) 是非匹配点，此时 \(x\to y\) 构成一条增广路，非匹配边的数量已经比匹配边数量多 \(1\)。
  • \((u,y)\) 是已匹配边，且 \((u,v)\) 是未匹配但合法的边，此时 \(x\to y\to u\to v\) 构成一条增广路。

在实现中，我们依次令 \(1\sim n\) 内 所有的非匹配点 作为起始点 \(x\) 尝试找到任何一条增广路。当碰到任意非匹配点时结束（增广路判定：起点与终点均为非匹配点），否则向 该匹配点匹配的点 继续搜索。

也就是说，一层 DFS 会寻找一条非匹配边并作为起点，产生以下两种行为：

  1. 该非匹配边终点为非匹配点，以该匹配边结束增广路。
  2. 经过该非匹配边后还能再找到一条匹配边（若情况 1 不满足，显然一定能找到这样一条边），则在终点进行下一层 DFS，寻找下一条非匹配边。

时间复杂度为 \(\mathcal O(n^2+nm)\)，但一般二分图题目的 \(X\) 与 \(Y\) 部间的连边偏稠密，所以简化为 \(\mathcal O(nm)\)。

bool Find(int x) {
	vis[x] = now; // 时间戳标记
	for (auto i : g[x]) {
		if (vis[i] == now) // 不经过访问过的 i
			continue;
		if (!mat[i] /* 非匹配点，即终点 */ ||
			(vis[mat[i]] != now /* mat[i] 未访问过，可以经过 */
			&& Find(mat[i]) /* 可找到增广路 */)) {
			mat[i] = x; // 匹配
			return 1;
		}
	}
	return 0;
}
inline int Hungary(int n) {
	int res = 0;
	for (int i = 1; i <= n; ++i) {
		++now;
		res += Find(i);
	}
	return res;
}

一般来说，二分图题目对点、边、分组方法和匹配范围的识别较为模糊。但一般的二分图题目都会有一些特点：

  • 结点能分为两组，且各组内结点间没有连边
  • 每个结点只能与一条边匹配

有时候，题目要求判定是否存在 「完备匹配」，也就是说，\(ans=n\)。即任意一次 find(i) 返回 false 时，完备匹配不存在。

最后给出与匈牙利算法有关的两个问题：

  1. 最小点覆盖：给定一个二分图，求出一个最小的点集，使得这个点集发出的所有边可以覆盖整个二分图。

    定理：该点集的大小是二分图的最大匹配包含的边数。

  2. 最大独立集：给定一个无向图，求出一个最大的点集，使得该点集中的所有点两两之间没有边相连。

    定理：当该无向图是二分图时，最大独立集的大小等于 \(n\) 减去最大匹配数。

    证明：由于最小点覆盖可以覆盖所有边，故不存在两个点，使得它们不属于最小点覆盖且有连边。

    所以，当去掉最小点覆盖后，剩余点两两之间没有连边。因为最小点覆盖大小就是最大匹配大小，故原命题成立。

KM 算法

还没写…… 咕咕咕

A. Ants

https://vjudge.net/contest/554888#problem/A

板板题。把黑蚂蚁和白蚂蚁按欧几里得距离连边后 KM 即可。

namespace XSC062 {
using namespace fastIO;
typedef double db;
const db inf = 1e18;
const db eps = 1e-5;
const int maxn = 205;
int n, now;
db g[maxn][maxn];
db u[maxn], up[maxn];
int vis[maxn], mat[maxn];
int a[maxn][2], b[maxn][2];
inline db max(db x, db y) {
	return x > y ? x : y;
}
inline db min(db x, db y) {
	return x < y ? x : y;
}
inline bool eq(db x, db y) {
	return fabs(x - y) <= eps;
}
bool Find(int x) {
	vis[x] = now;
	for (int i = n + 1; i <= 2 * n; ++i) {
		if (vis[i] == now)
			continue;
		if (eq(u[x] + u[i], g[x][i])) {
			vis[i] = now;
			if (!mat[i] || (vis[mat[i]] != now
							&& Find(mat[i]))) {
				mat[i] = x;
				return 1;
			}
		}
		else {
			up[i] = min(up[i],
				u[x] + u[i] - g[x][i]);
		}
	}
	return 0;
}
inline void Solve(void) {
	for (int i = 1; i <= n; ++i) {
		u[i] = -inf;
		for (int j = n + 1; j <= 2 * n; ++j)
			u[i] = max(u[i], g[i][j]);
	}
	for (int i = 1; i <= n; ++i) {
		for (;;) {
			++now;
			for (int j = n + 1; j <= 2 * n; ++j)
				up[j] = inf;
			if (Find(i))
				break;
			db Delta = inf;
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] != now)
					Delta = min(Delta, up[j]);
			}			for (int j = 1; j <= n; ++j) {
				if (vis[j] == now)
					u[j] -= Delta;
			}
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] == now)
					u[j] += Delta;
			}
		}
	}
	return;
}
inline db dist(int x1, int y1, int x2, int y2) {
	return sqrt((db)(x1 - x2) * (x1 - x2) +
					(y1 - y2) * (y1 - y2));
}
int main() {
	read(n);
	for (int i = 1; i <= n; ++i)
		read(a[i][0]), read(a[i][1]);
	for (int i = 1; i <= n; ++i)
		read(b[i][0]), read(b[i][1]);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			g[j][i + n] = -dist(a[i][0], a[i][1],
							b[j][0], b[j][1]);
		}
	}
	Solve();
	for (int i = n + 1; i <= 2 * n; ++i)
		print(mat[i], '\n');
	return 0;
}
} // namespace XSC062

B. 奔小康赚大钱

https://vjudge.net/contest/554888#problem/B

板板题。把居民和房子连边即可。

namespace XSC062 {
using namespace fastIO;
const int maxn = 605;
const int inf = 0x3f3f3f3f;
int n, now, res;
int g[maxn][maxn];
int u[maxn], up[maxn];
int vis[maxn], mat[maxn];
inline int max(int x, int y) {
	return x > y ? x : y;
}
inline int min(int x, int y) {
	return x < y ? x : y;
}
bool Find(int x) {
	vis[x] = now;
	for (int i = n + 1; i <= 2 * n; ++i) {
		if (vis[i] == now)
			continue;
		if (u[x] + u[i] == g[x][i]) {
			vis[i] = now;
			if (!mat[i] || (vis[mat[i]] != now
							&& Find(mat[i]))) {
				mat[i] = x;
				return 1;
			}
		}
		else {
			up[i] = min(up[i],
				u[x] + u[i] - g[x][i]);
		}
	}
	return 0;
}
inline void Solve(void) {
	for (int i = 1; i <= 2 * n; ++i)
		mat[i] = u[i] = 0;
	for (int i = 1; i <= n; ++i) {
		u[i] = -inf;
		for (int j = n + 1; j <= 2 * n; ++j)
			u[i] = max(u[i], g[i][j]);
	}
	for (int i = 1; i <= n; ++i) {
		for (;;) {
			++now;
			for (int j = n + 1; j <= 2 * n; ++j)
				up[j] = inf;
			if (Find(i))
				break;
			int Delta = inf;
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] != now)
					Delta = min(Delta, up[j]);
			}
			for (int j = 1; j <= n; ++j) {
				if (vis[j] == now)
					u[j] -= Delta;
			}
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] == now)
					u[j] += Delta;
			}
		}
	}
	return;
}
int main() {
	while(read(n)) {
		res = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j)
				read(g[i][j + n]);
		}
		Solve();
		for (int i = n + 1; i <= 2 * n; ++i)
			res += g[mat[i]][i];
		print(res, '\n');
	}
	return 0;
}
} // namespace XSC062

C. Going Home

https://vjudge.net/contest/554888#problem/C

板板题。把人和房子按曼哈顿距离连边即可。

namespace XSC062 {
using namespace fastIO;
const int maxn = 205;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn];
char s[maxn][maxn];
int u[maxn], up[maxn];
int h, w, n, m, now, res;
int vis[maxn], mat[maxn];
int a[maxn][2], b[maxn][2];
inline int max(int x, int y) {
	return x > y ? x : y;
}
inline int min(int x, int y) {
	return x < y ? x : y;
}
bool Find(int x) {
	vis[x] = now;
	for (int i = n + 1; i <= 2 * n; ++i) {
		if (vis[i] == now)
			continue;
		if (u[x] + u[i] == g[x][i]) {
			vis[i] = now;
			if (!mat[i] || (vis[mat[i]] != now
							&& Find(mat[i]))) {
				mat[i] = x;
				return 1;
			}
		}
		else {
			up[i] = min(up[i],
				u[x] + u[i] - g[x][i]);
		}
	}
	return 0;
}
inline void Solve(void) {
	for (int i = 1; i <= 2 * n; ++i)
		mat[i] = u[i] = 0;
	for (int i = 1; i <= n; ++i) {
		u[i] = -inf;
		for (int j = n + 1; j <= 2 * n; ++j)
			u[i] = max(u[i], g[i][j]);
	}
	for (int i = 1; i <= n; ++i) {
		for (;;) {
			++now;
			for (int j = n + 1; j <= 2 * n; ++j)
				up[j] = inf;
			if (Find(i))
				break;
			int Delta = inf;
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] != now)
					Delta = min(Delta, up[j]);
			}
			for (int j = 1; j <= n; ++j) {
				if (vis[j] == now)
					u[j] -= Delta;
			}
			for (int j = n + 1;
							j <= 2 * n; ++j) {
				if (vis[j] == now)
					u[j] += Delta;
			}
		}
	}
	return;
}
inline int abs(int x) {
	return x >= 0 ? x : -x;
}
inline int dist(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1- y2);
}
inline void Init(void) {
	res = n = m = 0;
	memset(g, 0, sizeof (g));
	return;
}
int main() {
	scanf("%d %d", &h, &w);
	while (h || w) {
		Init();
		for (int i = 1; i <= h; ++i) {
			scanf("%s", s[i] + 1);
			for (int j = 1; j <= w; ++j) {
				if (s[i][j] == 'H')
					a[++n][0] = i, a[n][1] = j;
				else if (s[i][j] == 'm')
					b[++m][0] = i, b[m][1] = j;
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				g[i][j + n] = -dist(a[i][0],
					a[i][1], b[j][0], b[j][1]);
			}
		}
		Solve();
		for (int i = n + 1; i <= 2 * n; ++i)
			res += g[mat[i]][i];
		print(-res, '\n');
		scanf("%d %d", &h, &w);
	}
	return 0;
}
} // namespace XSC062

D. Cyclic Tour

https://vjudge.net/contest/554888#problem/D

题意在讲什么啊，看了半天看不懂，网上找了 TJ 才看懂题意。

给定一个有向图，找到若干个互不相交的环覆盖整个图，使得所有环上边权和最小，若找不到方案输出 -1。

我们知道与这道题相类似的最小路径覆盖问题可以用二分图 + 拆点来解决。

标签：二分,匹配,增广,int,230502,maxn,归档,return
From： https://www.cnblogs.com/XSC062/p/17367424.html

相关文章

  • 「TJOI2018」智力竞赛（二分+DAG最小可相交路径覆盖）
    https://loj.ac/problem/2574这个题目描述扎心了。简要题意：用n+1条可以相交的路径去覆盖DAG，使得没被覆盖的点的权值的最小值最大。首先二分答案，问题转换为有一些点一定要被覆盖，问n+1条路径内有没有解。这个可以暴力费用流，每个点拆成两个点，\(i->i',r=1\)，如果这个点必选，则费用为inf，......
  • 二分查找——出现溢出问题
    算法描述：前提：有已排序数组A（假设已经做好）定义左边界L、右边界R，确定搜索范围，循环执行二分查找（3、4两步）获取中间索引M=Floor((L+R)/2)中间索引的值A[M]与待搜索的值T进行比较①A[M]==T表示找到，返回中间索引②A[M]>T，中间值右侧的其它元素都大于T，无需......
  • 【二分查找】LeetCode 33. 搜索旋转排序数组思路
    题目链接33.搜索旋转排序数组思路思路都在注释里代码classSolution{publicintsearch(int[]nums,inttarget){intlen=nums.length;if(len==0){return-1;}intleft=0,right=len-1;//1.......
  • 【二分查找】LeetCode 528. 按权重随机选择
    题目链接528.按权重随机选择思路代码classSolution{privateint[]sum;publicSolution(int[]w){sum=newint[w.length+1];for(inti=1;i<sum.length;i++){sum[i]=sum[i-1]+w[i-1];}}p......
  • 【二分查找】LeetCode 69. x 的平方根
    题目链接69.x的平方根思路基本思路是在区间\([1,x/2]\)中使用二分查找（因为平方根必然小于\(x/2\)），只不过需要注意一些细节。因为使用的是闭区间查找，所以判断循环终止的条件为\(left\leqright\)。为了防止溢出，使用mid=(right-left)/2+left和mid==x/mi......
  • 【二分查找】LeetCode 540. 有序数组中的单一元素
    题目链接540.有序数组中的单一元素思路假如不存在单个的元素，那么在奇数位置上总是成对元素的第一个元素，偶数位置上总是成对元素的第二个元素，但是如果加入了单个元素呢？我们可以看到在单个元素的左边这个特点没有变化，但是在单个元素的右边，奇数位置上总是成对元素的第二个元素，偶......
  • LeetCode 704. 二分查找 题解
    本题考查的就是一个基本的整数二分查找问题对于整数二分，有单调性一定可以二分，没有单调性的有时候也可以二分。算法思想（分为两种方法）：查找结果是在左边区间的情况区间被划分为[l,mid]和[mid+1,r]1、确定分界点，mid=q[(l+r)/2]2、判断是否满足是：区间变成[l,mid]因此：r=mid否......
  • sklearn.metrics.precision_recall_curve—计算不同概率阈值的精确召回对（仅限于二分类
    参考：https://scikit-learn.org/stable/modules/generated/sklearn.metrics.precision_recall_curve.html在分类模型的性能评估指标总结章节中，提到的Precision-Recall曲线可通过sklearn库中的precision_recall_curve函数计算而得。语法格式sklearn.metrics.precision_recall_cu......
  • Chemistry Experiment Codeforces Round 247 (Div. 2) 线段树动态开点，二分
    第一次写的时候还不会线段树的动态开点，写了一个是线段树但是是\(O(N^2)\)的写法，现在用动态开点武装了自己，会了正解\(O(qlogn^2)\)。首先建立一个权值线段树，但这里的权值很大，通过动态开点去建树来节省空间，对于两种操作：操作1，常见的动态开点的单点修改操作2，二分答案，然后在线段树......
  • 【dp的二分优化】NO300 最长递增子序列
    【dp的二分优化】300.最长递增子序列给你一个整数数组nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1：输入：nums=[10,9,2,5,3,7,101,18]......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99