首页 > 代码库 > POJ 2226 缩点建图+二分图最大匹配
POJ 2226 缩点建图+二分图最大匹配
这个最小覆盖但不同于 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。