首页 > 代码库 > 二分图

二分图

2024-07-11 07:11:10   228人阅读

将前两天学的二分图写个博文吧。。

二分图的概念就不讲了，这里只说算法及要注意的地方

PS：有些是在日记上写的，所以不管逻辑啥的，我搬上来了。。

匈牙利算法（最大匹配带最小覆盖输出方案）：

#include <cstdio>#include <cstring>using namespace std;#define FOR(i,a,n) for(i=a;i<=n;++i)#define CC(a) memset(a,0,sizeof(a))const int maxn=505;bool visx[maxn], visy[maxn];int xm[maxn], ym[maxn]; //xm是x对应的y，ym是y对应的xint ihead[maxn], inext[maxn*maxn], iv[maxn*maxn], cnt=1;bool ifind(int x) {	int y, i;	visx[x]=true; //这个用来打印最小覆盖用的	for(i=ihead[x]; i; i=inext[i]) if(!visy[y=iv[i]]) {		visy[y]=true;		if(!ym[y] || ifind(ym[y])) {			ym[y]=x;			xm[x]=y;			return true;		}	}	return false;}int main() {	int i, a, b, m, ans, n, n1;	while(~scanf("%d%d%d", &n, &m, &n1)) {		CC(xm); CC(ym); CC(ihead); ans=0; cnt=1;		FOR(i, 1, m) {			scanf("%d%d", &a, &b);			inext[++cnt]=ihead[a]; ihead[a]=cnt; iv[cnt]=b;		}		FOR(i, 1, n1-1) if(!xm[i]) {			CC(visx); CC(visy);			if(ifind(i)) ans++;		}		//输出最小覆盖的方案，最小覆盖的求法		//首先从之前匈牙利树中X集中未盖点再开始用匈牙利拓展，标记访问过的x和y，那么解就是X中未标记的和Y中标记的。		CC(visx); CC(visy);		FOR(i, 1, n1-1) if(!xm[i]) ifind(i);		FOR(i, 1, n1-1) if(!visx[i]) printf("%d ", i);		printf("\n");		FOR(i, n1, n) if(visy[i]) printf("%d ", i);		printf("\n");		printf("max num:%d\n", ans);	}	return 0;}

 

KM算法（求最大权值的完全匹配）：

这里要注意，二分图必须是完全二分图，即保证X集和Y集的所有元素都匹配。

PS：由于n^3的算法是用bfs，太难写了，暂时我先不写，n^4就这样吧。。

#include <cstdio>#include <cstring>using namespace std;#define FOR(i,a,n) for(i=a;i<=n;++i)#define CC(a) memset(a,0,sizeof(a))#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))const int maxn=505, oo=~0u>>1;bool visy[maxn], visx[maxn];int my[maxn], lx[maxn], ly[maxn];int ihead[maxn], inext[maxn*maxn], iv[maxn*maxn], iw[maxn*maxn], cnt;int e;bool ifind(int x) {	int y, i;	visx[x]=true; //跟着顶标走，只有这样才能保证图的最大权	for(i=ihead[x]; i; i=inext[i]) if(lx[x]+ly[y=iv[i]]==iw[i] && !visy[y]) {		visy[y]=true;		if(!my[y] || ifind(my[y])) {			my[y]=x;			return true;		}	}	return false;}void update(int n) {	int i, j, a=oo;	FOR(i, 1, n) if(visx[i]) //从X集访问过的找Y集未访问过的，更新顶标		for(j=ihead[i]; j; j=inext[j]) if(!visy[iv[j]])			a=min(a, lx[i]+ly[iv[j]]-iw[j]);	FOR(i, 1, n) {		if(visx[i]) lx[i]-=a; //顶标更新		if(visy[i]) ly[i]+=a;	}}int KM(int n) {	CC(lx); CC(ly); CC(my);	int i, j, ans=0; e=0;	FOR(i, 1, n) for(j=ihead[i]; j; j=inext[j])		lx[i]=max(lx[i], iw[j]);	FOR(i, 1, n) while(1) {		CC(visx); CC(visy);		if(ifind(i)) { e++; break; } else update(n<<1);	}	FOR(i, 1, n) ans+=lx[i];	FOR(i, n+1, n<<1) ans+=ly[i];	return ans;}int main() {	int i, a, b, c, n, m, ans;	//PS：我这个自己出的数据很坑啊。。只有X集的个数，所以用邻接表建图的要注意传到KM的n要是2倍大的。。	while(~scanf("%d%d", &n, &m)) {		CC(ihead); cnt=1;		FOR(i, 1, m) {			scanf("%d%d%d", &a, &b, &c);			inext[++cnt]=ihead[a]; ihead[a]=cnt; iv[cnt]=b+n; iw[cnt]=c;		}		ans=KM(n);		printf("max edge:%d\nmax num:%d\n", e, ans);	}	return 0;}

 

我自己的无脑理解：

  • 为什么

    if(!my[y] || ifind(my[y])) {
    　　my[y]=x;
    　　return true;
    }

    这样就能找到增广路？

    　　其实很简单，找增广路的时候，是按照x的顺序下来的，如果x呗找过，那么可以跳过这个点，不找，因而每次调用ifnd的x都是未盖点
    从这个未盖点出发，可能走了几条匹配边，但都不会在这个if内判断为真，所以一定会循环到未匹配边上。
    　　1、而到了这个未匹配边上的点，有可能是匹配点也有可能是未盖点，如果是未盖点，那么循环一次就退出了，因为找到了一条增广路了嘛。
    　　如果是匹配点，没关系，下一次循环是my[y]，是一条增广路上的x，此时就跳到了上面的步骤1、这里，只不过走的弧一定是未匹配弧。
    　　因此，第一次跑的一定是未匹配边，最后一次跑的也是未匹配边，中间一定是一条增广路的匹配弧。

  • KM算法，为什么顶标可行？

    　　因为顶标lx[u]和ly[v]的和是u点开始的最大弧的边权。在找到一个相等子图后，设子图内x号点为S，y号点为T，x内除S外的点集为S‘，y内除T外的点集为T‘。因为相等子图内匹配弧lx[u]+ly[v]一定是u和v之间的弧，由顶标的定义可知，这是最大权的弧，那么我们就要找一个相等子图，使得它完全匹配。这就要求要修改顶标，否则无法加入新边到相等子图中去。
    　　修改的思想很简单，如果从x中某个点u出发没有在匈牙利算法找到满足lx[u]+lx[v]==w[u][v]的增广路，那么就要修改顶标，因为是从u开始的增广路，因此要先修改u的顶标，因为我们要尽量将所有边都可能地加入到相等子图中去，所以我们要将顶标修改为从u开始的第二大权值的弧，以此类推，第三大、第四大。。。
    　　就是从u开始找相等子图中所有的x的min{lx[u]+ly[v]-w[u][v]}为它要减小的量，其中这个v不能在相等子图中，因为我们要加入的弧是要在相等子图之外的，然后在以往的lx基础上剪掉。因为要满足lx[u]+lx[v]==w[u][v]，所以所有的lx[v]要加上这个量。然后继续找增广路。这样有可能加入一条弧到相等子图内，也可能不加，那么又要这样找下去。

  • 一些知识：

    　　只有在保证图为完全二分图的情况下才能用KM算法找最大权的完美匹配，因为如果原二分图不是完全二分图，那么KM算法会陷入死循环。因为你一直找不到增广路，一直修改顶标，都没有用。所以这种情况只能用最大费用最大流来搞。

  • 最小点覆盖=最大匹配

    　　这个我不证了（其实也不会- -），看一篇博文吧。http://www.matrix67.com/blog/archives/116
    我只说怎么构造解，（根据白书）
    　　首先从之前匈牙利树中X集中未盖点再开始用匈牙利拓展，标记访问过的x和y，那么解就是X中未标记的和Y中标记的。

  • 最大独立集=n-最大匹配

    　　就是一个V的子集V‘，假设u属于V‘，v属于V‘，不存在一条弧(u, v)或(v, u)。设最大匹配中有a条弧，那么我们只选这a条弧的a个节点即可，不可能选择>a个节点，否则不满足独立集的定义。再加上未盖点，就是一个最大独立集。（其实就是将最大匹配的其中一个节点去掉就行了，所以答案是n-最大匹配）

  • 最小路径覆盖=最大独立集

    　　这个定义我理解了好久额。。。我当时不知道这个最小路径覆盖有什么用。。其实就是最小点覆盖反过来定义而已。。选择最少的边，使得这些边没有相同的节点（没有节点相交）。这里要注意，每一个独立点都看作一条弧，距离为0的弧。所以这样很好看啦，其实就和最大独立集一样的。


联系
我们