忍不住再水一道 这是我第一次完全是自己转化出来的二分匹配题 先说好代码丑 臭 长 想看简介的还是点下标签的 叉叉 吧
但毕竟是自己的亲儿子 蛤蛤

因为这题的矩阵范围是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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最大匹配

HDU 1350 Taxi Cab Scheme

题意: 老司机接客的故事 有很多顾客想要去一些地方 给你起点和终点 问 Read more…

最大匹配

HDU 1498 50 years, 50 colors

尽管是大水题 但是再怎么说就是自己走过的路啊 不过现在只是二分图入门阶 Read more…

最大匹配

FZU 2039 Pets

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈 Read more…