匹配及其相关问题（三）

时间：2022-09-02 06:28:08

前言：
第二篇博客介绍了匈牙利算法解二分图最大匹配，这次我们需要应用这个算法来解决最小点覆盖与最大点独立问题。

基本定理：
根据博客（一），我们有以下定理：
定理3：二分图中，无孤立点，点覆盖数=边独立数（匹配数）
定理8：无向图中，无孤立点，最小点覆盖集与最大点独立集互补
我们这次需要使用这两个定理来解决最小点覆盖与最大点独立问题。

算法思路：
根据定理3，我们有点覆盖数等于匹配数，那么我们可以认为，最小点覆盖集与最大匹配之间有一种一一对应的关系。
最小点覆盖：
在求解完二分图匹配之后，我们可以知道现在二分图中已经没有增广路了，而且只存在两种边，第一种为两端都是已匹配点，第二种为一端已匹配、另一端未匹配。那么我们要找的最小点覆盖集肯定可以在所有的匹配点里找到，即对第一种边，随便挑一个点；对第二种边，挑匹配点。
那么我们怎么选这些匹配点呢？因为所有与未匹配点相连的点都应该是最小点覆盖集里的点，那么跟这些点匹配的点当然是不需要在最小点覆盖集里了。我们可以把二分图分成两部分，即左边和右边，我们可以使用匈牙利算法从未匹配点开始寻找增广路，对图中的点进行标记，最终左边未标记的点和右边标记了的点组成了最小点覆盖。
其实也可以分类讨论考虑最小点覆盖问题，即左边有未标记点和左边无未标记点。对于第一种情况，我直接左边的所有点组成的点集组成最小点覆盖；对于第二种情况，我们则是为了找到所有能覆盖未标记点所在的边而进行匈牙利的match操作，即我们发现最小点覆盖中不可能有这个点，于是就去找能够覆盖该点所有关联边的代替点集合。
最大点独立：
既然我们知道最小点覆盖，那么根据定理8，我们只需要求出最小点覆盖的补集就是最大点独立了，即标记了的左边点和未标记的右边点。

例题解析：
1、二分图最小点覆盖：
题目链接：UVA 11419
解题思路：
二分图最小点覆盖模板题。把每一行变成左边的点，每一列变成右边的点，这样就变成了最小点覆盖问题，可用上述算法解决。
代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 1005

using namespace std;

int n,m,K,a[maxn][maxn],vx[maxn],vy[maxn],prex[maxn],prey[maxn];

bool dfs(int index)
{
    vx[index]=1;
for(int i=1;i<=m;i++)
    {
if(!vy[i]&&a[index][i])
        {
            vy[i]=1;
if(!prey[i] || dfs(prey[i]))
            {
                prey[i]=index;
                prex[index]=i;
return 1;
            }
        }
    }
return 0;
}

int hungary()
{
int ans=0;
memset(prex,0,sizeof(prex));
memset(prey,0,sizeof(prey));
for(int i=1;i<=n;i++)
    {
memset(vy,0,sizeof(vy));
if(dfs(i))
            ans++;
    }
return ans;
}

int solve()
{
printf("%d",hungary());
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
for(int i=1;i<=n;i++)
if(!prex[i])
            dfs(i);
for(int i=1;i<=n;i++)
if(!vx[i])
printf(" r%d",i);
for(int i=1;i<=m;i++)
if(vy[i])
printf(" c%d",i);
printf("\n");
}

int main()
{
while(~scanf("%d %d %d",&n,&m,&K)&&n+m+K)
    {
memset(a,0,sizeof(a));
int x,y;
while(K--)
        {
scanf("%d %d",&x,&y);
            a[x][y]=1;
        }
        solve();
    }

return 0;
}

2、二分图最大点独立：
题目链接：UVALIVE 4288
解题思路：
二分图最大点独立，因为只需要求点独立数，所以直接套用匈牙利算法即可。构图方面，把所有人分成两类，喜欢猫的和喜欢狗的，形成二分图，并把所有存在矛盾关系的人连一条边，即讨厌对方喜欢的动物或者喜欢对方讨厌的动物。
代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 505

using namespace std;

int n,m,c,d,K,a[maxn][maxn],vy[maxn],prey[maxn];
int likec[maxn],liked[maxn],hatec[maxn],hated[maxn];

bool dfs(int index)
{
for(int i=1;i<=m;i++)
    {
if(!vy[i]&&a[index][i])
        {
            vy[i]=1;
if(!prey[i] || dfs(prey[i]))
            {
                prey[i]=index;
return 1;
            }
        }
    }
return 0;
}

int hungary()
{
int ans=0;
memset(prey,0,sizeof(prey));
for(int i=1;i<=n;i++)
    {
memset(vy,0,sizeof(vy));
if(dfs(i))
            ans++;
    }
return ans;
}

int main()
{
int T;
scanf("%d",&T);
    getchar();
while(T--)
    {
        n=m=0;
scanf("%d %d %d",&c,&d,&K);
        getchar();
char ch1,ch2;
int x,y;
for(int i=1;i<=K;i++)
        {
scanf("%c%d %c%d",&ch1,&x,&ch2,&y);
if(ch1=='C')
            {
                n++;
                likec[n]=x,hated[n]=y;
            }
else
            {
                m++;                
                liked[m]=x,hatec[m]=y;
            }
            getchar();
        }

memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
        {
for(int j=1;j<=m;j++)
            {
if(likec[i]==hatec[j] || liked[j]==hated[i])
                {
                    a[i][j]=1;
                }
            }
        }

int ans=hungary();
printf("%d\n",n+m-ans);
    }

return 0;
}

参考资料：
Matrix 67的博客
标签：

相关文章