忍不住再水一道 这是我第一次完全是自己转化出来的二分匹配题 先说好代码丑 臭 长 想看简介的还是点下标签的 叉叉 吧
但毕竟是自己的亲儿子 蛤蛤
因为这题的矩阵范围是4*4 特别小 暴搜也是随便过的 这里我就不贴了 和之前写的一道超暴力回溯差不多 但是简单的很多
还是讲讲二分的吧 如果是平时一对一的匹配 只要 把行看成一个集合 把列看成一个集合进行匹配即可 但这里一行可以与多列匹配 一列与多行匹配 需要重新建图
我的烂思路就是再开两个矩阵 一个记录新的 行 一个记录新的列 再建立方向矩阵 套模板即可
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,nrow,ncol;
const int maxn=16;
bool g[maxn][maxn],vis[maxn];
char mat[maxn][maxn];
int row[maxn][maxn],col[maxn][maxn],link[maxn];
int hungary();
int dfs(int x);
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
getchar();
for(int i=1; i<=n; i++) scanf("%s",mat[i]+1);
int num=1,flag[3];
for(int i=1; i<=n; i++)//建立行矩阵
{
flag[0]=flag[1]=flag[2]=0;
for(int j=1; j<=n; j++)
if(mat[i][j]=='X')
{
row[i][j]=0;
flag[1]=j;
}
else
{
if(flag[0]&&flag[1]&&flag[0]<flag[1])//如果同时存在.和X 并且 . 在X 前面
{
row[i][j]=n+num;
flag[2]=1;
}
else row[i][j]=i;
if(!flag[0]) flag[0]=j;
}
if(flag[2]) num++;
}
nrow=n+num-1;//新行长度
num=1;
for(int i=1; i<=n; i++)//建立新列 与上相同
{
flag[0]=flag[1]=flag[2]=0;
for(int j=1; j<=n; j++)
if(mat[j][i]=='X')
{
col[j][i]=0;
flag[1]=j;
}
else
{
if(flag[0]&&flag[1]&&flag[0]<flag[1])
{
col[j][i]=n+num;
flag[2]=1;
}
else col[j][i]=i;
if(!flag[0]) flag[0]=j;
}
if(flag[2]) num++;
}
ncol=n+num-1;
memset(g,false,sizeof g);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[row[i][j]][col[i][j]]=true;//建立邻接矩阵
g[0][0]=false;
int ans=hungary();//套模板
printf("%d\n",ans);
}
return 0;
}
int hungary()
{
int num=0;
memset(link,-1,sizeof link);
for(int i=1;i<=nrow;i++)
{
memset(vis,false,sizeof vis);
num+=dfs(i);
}
return num;
}
int dfs(int x)
{
for(int i=1;i<=ncol;i++)
if(!vis[i]&&g[x][i])
{
vis[i]=true;
if(link[i]==-1||dfs(link[i]))
{
link[i]=x;
return 1;
}
}
return 0;
}