二分图三·二分图最小点覆盖和最大独立集
- 时间限制:10000ms
- 单点时限:1000ms
- 内存限制:256MB
描述
在上次安排完相亲之后又过了挺长时间，大家好像都差不多见过面了。不过相亲这个事不是说那么容易的，所以Nettle的姑姑打算收集一下之前的情况并再安排一次相亲。所以现在摆在Nettle面前的有2个问题：
1.姑姑想要了解之前所有相亲的情况。对于任一个一次相亲，只要跟参与相亲的两人交流就可以得到这次相亲的情况。如果一个人参加了多次相亲，那么跟他交流就可以知道这几次相亲的情况。那么问题来了，挖掘技术到底哪家强姑姑最少需要跟多少人进行交流可以了解到所有相亲的情况。
问题1解答
同样的转化为图G=(V,E)，则问题转化为： 在图G中选取尽可能少的点，使得图中每一条边至少有一个端点被选中。 这个问题在二分图问题中被称为最小点覆盖问题。即用最少的点去覆盖所有的边。 结论：由König定理可知最小点覆盖的点数 = 二分图最大匹配 戳这里可以看到一个简单易懂的证明
2.因为春节快要结束了，姑姑打算给这些人再安排一次集体相亲。集体相亲也就是所有人在一起相亲，不再安排一对一对的进行相亲。但是姑姑有个条件，要求所有参与相亲的人之前都没有见过。也就是说在之前的每一次相亲中的两人不会被同时邀请来参加这次集体相亲。那么问题又来了，姑姑最多可以让多少人参与这个集体相亲。
问题2解答
依旧转化为图G=(V,E)，则问题转化为：
在图G中选取尽可能多的点，使得任意两个点之间没有连边。
这个问题在二分图问题中被称为最大独立集问题。
结论：最大独立集的点数 = 总点数 - 二分图最大匹配
证明：
假设最大独立集的点数为|U|，二分图最大匹配的匹配数为|M|，最大匹配中所有顶点集合为EM
先证明 |U|≤|V|-|M|
M中任意一条边的两个端点是连接的，所有对于M中的边必有一个端点不在|U|集合中，所以|M|≤|V|-|U|
再证明|U|≥|V|-|M|
首先我们知道一定有|U|≥|V|-|EM|，即将最大匹配的点删除之后，剩下的点一定都不相连。
接下来我们考虑能否将M集合中的一个端点放入U中：
假设(x,y)属于M，存在(a,x),(b,y)，且a,b都在U中，则会出现两种情况：
如果(a,b)连接，则有一个更大的匹配存在，矛盾
如果(a,b)不连接，a->x->y->b有一个新的增广路，因此有一个更大的匹配，矛盾
故有a,b两点中至多只有1个点属于U，则我们总是可以选取x,y中一个点放入集合U
所以|U|≥|V|-|EM|+|M|=|V|-|M|
综上有
|U|=|V|-|M|
输入
第1行：2个正整数，N,M(N表示点数 2≤N≤1,000，M表示边数1≤M≤5,000)
第2..M+1行：每行两个整数u,v，表示一条无向边(u,v)
输出
第1行：1个整数，表示最小点覆盖数
第2行：1个整数，表示最大独立集数
样例输入
5 4
3 2
1 3
5 4
1 5样例输出
2
3链接
http://hihocoder.com/problemset/problem/1127
题意
求图的最小点覆盖和最大独立集。
题解
转化为二分图匹配问题。
- 最小点覆盖的点数 = 二分图最大匹配
- 最大独立集的点数 = 总点数 - 二分图最大匹配
代码
| Status | Accepted |
|---|---|
| Time | 5ms |
| Length | 1464 |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
const int maxm = 5010;
int n, m, tot;
bool vis[maxn];
int head[maxn], match[maxn];
struct Edge
{
int to, next;
}edge[maxm<<1];
void init()
{
tot = 0;
memset(vis, 0, sizeof(vis));
memset(match, 0, sizeof(match));
memset(head, -1, sizeof(head));
}
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
bool find(int u) // 匈牙利算法
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (!vis[v]) // 未标记过
{
vis[v] = true;
if (!match[v] || find(match[v])) // 没有匹配过或者能腾出位置来
{
match[v] = u;
match[u] = v;
return true;
}
}
}
return false;
}
int main()
{
int u, v;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
{
memset(vis, 0, sizeof(vis));
if (!match[i]) // 当前还未匹配，不判断的话会重复计算
{
if (find(i)) // 每次匹配一个累加一个
ans++;
}
}
printf("%d\n%d\n", ans, n - ans); // 最小点覆盖于最大独立集
}
return 0;
}The end.
2018-08-01 星期三
二分图最大匹配的König定理及其证明
转载自Matrix67，原文链接：传送门
本文将是这一系列里最短的一篇，因为我只打算把König定理证了，其它的废话一概没有。
以下五个问题我可能会在以后的文章里说，如果你现在很想知道的话，网上去找找答案：
- 什么是二分图；
- 什么是二分图的匹配；
- 什么是匈牙利算法；
- König定理证到了有什么用；
- 为什么o上面有两个点。
König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。比如，下面这个图中的最大匹配和最小点覆盖已分别用蓝色和红色标注。它们都等于3。这个定理相信大多数人都知道，但是网络上给出的证明并不多见。有一些网上常见的“证明”明显是错误的。因此，我在这里写一下这个定理的证明，希望对大家有所帮助。
假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。
匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。看图，右图中展示了两条这样的路径，标记了一共6个点（用 “√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。
首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。
其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。
最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。
证完了。