首页 > 代码库 > POJ 2226 缩点建图+二分图最大匹配

POJ 2226 缩点建图+二分图最大匹配

2024-07-07 03:13:48   225人阅读

这个最小覆盖但不同于 POJ 3041，只有横或者竖方向连通的点能用一块板子覆盖，非连续的，就要用多块

所以用类似并查集方法，分别横向与竖向缩点，有交集的地方就连通，再走一遍最大匹配即可

一开始还有点没想清楚缩点怎么写，其实就是横向和竖向分别缩一下，不要混在一起，否则很麻烦，要注意一下

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char mat[900][900];
int a[910][910],b[910][910],d[1100][1100];
int lefts[1100],vis[1100];
int r,c,nc,nr;
bool match(int u)
{
    for (int v=1;v<=nc;v++){
        if (d[u][v] && !vis[v]){
            vis[v]=1;
            if (lefts[v]==-1 || match(lefts[v])){
                lefts[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    while (scanf("%d%d",&r,&c)!=EOF)
    {

        memset(d,0,sizeof d);
        nc=0;nr=0;
        for (int i=1;i<=r;i++) scanf("%s",mat[i]+1);
        for (int i=1;i<=r;i++)
            for (int j=1;j<=c;j++){
                    if (mat[i][j]==‘*‘){
                        if (mat[i][j-1]==‘*‘) a[i][j]=a[i][j-1];
                        else a[i][j]=++nr;
                    }
                }
        for (int i=1;i<=r;i++){
          for (int j=1;j<=c;j++){
              if (mat[i][j]==‘*‘){
                if (mat[i-1][j]==‘*‘) b[i][j]=b[i-1][j];
                else b[i][j]=++nc;
                d[a[i][j]][b[i][j]]=1;
              }
        }
        }
        int ans=0;
        //cout<<nr<<" "<<nr<<endl;
        memset(lefts,-1,sizeof lefts);
        for (int i=1;i<=nr;i++){
            memset(vis,0,sizeof vis);
            if (match(i)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 


联系
我们