二分图之最小边覆盖（poj3020）

我不是女神ヾ 2022-08-27 14:54 155阅读 0赞

题目：[poj3020][]

题意：给出一个图，让你用最少的1\*2的纸片覆盖掉图中的所有\*出现过的地方。基本裸的最小边覆盖。

分析：

最小边覆盖 = 点总数 - 最大匹配

所以就是转化为求最大匹配。

跟前面一道题目很相似，也是相同的建图方法，奇偶性建图。

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int N = 1200;
    #define Del(x,y) memset(x,y,sizeof(x))
    int map[N][N],link[N],vis[N],vlink[N];
    char path[50][50];
    int line[50][50];
    int n,m,t,tmp1,tmp2;
    bool dfs(int x)
    {
        for(int i=1; i<tmp2; i++)
        {
            if(map[x][i]==1 && vis[i]==0)
            {
                vis[i]=1;
                if(link[i]==-1 || dfs(link[i]))
                {
                    link[i]=x;
                    return true;
                }
            }
        }
        return false;
    }
    void solve()
    {
        int ans=0;
        Del(link,-1);
        for(int i=1; i<tmp1; i++)
        {
            Del(vis,0);
            if(dfs(i))
                ans++;
        }
        //printf("%d\n",ans);
        printf("%d\n",tmp1+tmp2-ans-2);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        //freopen("Input.txt","r",stdin);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            Del(path,0);
            for(int i=1;i<=n;i++)
            {
                getchar();
                for(int j=1;j<=m;j++)
                    scanf("%c",&path[i][j]);
            }
            Del(line,-1);
            tmp1=1,tmp2=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(path[i][j]=='*')
                    {
                        if((i+j)%2==0)
                            line[i][j]=tmp1++;
                        else
                            line[i][j]=tmp2++;
                    }
                }
            }
    
            Del(map,0);
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=m; j++)
                {
                    if(path[i][j]=='*' && (i+j)%2==1)
                    {
                        if(line[i-1][j]>=1)
                            map[line[i-1][j]][line[i][j]]=1;
                        if(line[i+1][j]>=1)
                            map[line[i+1][j]][line[i][j]]=1;
                        if(line[i][j-1]>=1)
                            map[line[i][j-1]][line[i][j]]=1;
                        if(line[i][j+1]>=1)
                            map[line[i][j+1]][line[i][j]]=1;
                    }
                }
            }
            solve();
        }
        return 0;
    }

[poj3020]: http://poj.org/problem?id=3020