マッチングとその関連問題(三)

前言:第2編のブログではハンガリーアルゴリズム解二分図の最大マッチングを紹介し、今回はこのアルゴリズムを適用して最小点カバーと最大点独立問題を解決する必要がある.
基本定理:ブログ(一)によると、定理3:二分図では、孤立点なし、点被覆数=辺独立数(マッチング数)定理8:無方向図では、孤立点なし、最小点被覆セットと最大点独立セットが相補的である.今回は、この2つの定理を用いて、最小点被覆と最大点独立問題を解決する必要がある.
アルゴリズムの構想:定理3に基づいて、私たちは少しカバー数がマッチング数に等しいので、最小点カバーセットと最大マッチングの間には一つ一つ対応する関係があると考えることができます.最小点オーバーライド:二分図マッチングを解いた後、二分図には拡張路がなく、2つのエッジしか存在せず、1つ目は両端が一致点であり、2つ目は一端が一致し、もう一方の端が一致していないことがわかります.では、私たちが探している最小点カバーセットは、すべてのマッチングポイントで見つけることができます.つまり、最初のエッジに対して、勝手に点を選ぶことができます.2番目のエッジに対して、一致する点を選択します.では、どうやってこれらのマッチングポイントを選びますか?未一致点に接続されているすべての点が最小点オーバーライドセット内の点であるべきであるため、これらの点に一致する点はもちろん最小点オーバーライドセットには必要ありません.二分図を左と右の2つの部分に分けることができます.ハンガリーアルゴリズムを使用して、一致していない点を探し始め、図の中の点をマークし、最終的に左のマークされていない点と右のマークされた点が最小点カバーを構成することができます.実際には、左に未マークポイントがあるか、左に未マークポイントがないかという最小点オーバーライド問題を分類して議論することもできます.1つ目の場合、私は直接左のすべての点からなる点セットが最も小さな点で覆われています.第2の場合、私たちはマークされていない点があるすべてのエッジをカバーできるようにハンガリーの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("
");
}

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、二分図最大点独立:タイトルリンク:UVALLIVE 4288解題構想:二分図最大点独立、点独立数を求めるだけなので、ハンガリーアルゴリズムをそのまま適用すればよい.構図の面では、すべての人を2つに分けて、猫が好きな人と犬が好きな人を二分図にして、矛盾関係のあるすべての人を1つの辺につなぎます.つまり、相手の好きな動物が嫌いなのか、相手の嫌いな動物が好きなのか.コード:

#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+m-ans);
    }

    return 0;
}

参考資料:Matrix 67のブログ