题目描述

最大匹配<=> 不存在增广路径

思路

最多选多少条边，使得选出来的边没有公共点。
邻接矩阵匈牙利算法需要枚举四个方向，看看周围的点有没有匹配，或者能不能换匹配对象
因为在邻接矩阵中，矩阵里的点隔一个为一组，黑白黑白黑白…，因此对于一个点，他上下左右四个点一定和他不是同一组。

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;
const int N=110;

int n,m;
pii match[N][N];
int g[N][N],st[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int find(int x,int y)
{
    //遍历上下左右四个方向
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<1 || a>n ||b<1||b>n) continue;
        //如果a,b已被预定过或是坏点，continue
        if(st[a][b] || g[a][b]) continue;
        auto t=match[a][b];
        st[a][b]=1;
        //如果t.x(男生)是0，代表女生ab没有对象
        if(t.x ==0 || find(t.x,t.y))
        {
            //match[a][b]是男生，把他的值赋成x,y为男生，ab是女生
            match[a][b]={x,y};
            return 1;
        }
    }
    return 0;
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        //输入坏点
        int x,y;
        cin>>x>>y;
        g[x][y]=1;
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //枚举奇数点
            if((i+j)%2 && !g[i][j])
            {
                memset(st,0,sizeof st);
                if(find(i,j)) res++;
            }
        }
    }
    cout<<res;
    return 0;
}

二刷，一遍过，注意一些细节：

1. 匈牙利的退出条件为，只要给match[a][b]成功赋值，就返回1，做到最后都没有返回0
2. 相比于二染色，退出条件为做到最后返回1，中间出错只能返回0
3. 注意，find(x,y) x,y是男生，他的邻边ab是女生。match[a][b]返回的是男生，如果返回0则说明女生ab没有对象

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;
typedef pair<int,int> pii;

int g[N][N],st[N][N];
pii match[N][N];
int n,m;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


int find(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>n||a<1||b>n||b<1) continue;
        if(st[a][b]) continue;
        if(g[a][b]) continue;
        st[a][b]=1;
        auto t=match[a][b];
        // t为男生，[a][b]为女生， t.first==0意思为该女生没有匹配男生
        if(t.first==0 || find(t.first,t.second))
        {
            match[a][b]={x,y};
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            memset(st,0,sizeof st);
            if(g[i][j]) continue;
            if((i+j)%2 && find(i,j))
            {
                res++;
            }
        }
    }
    cout<<res;
    return 0;
}

三刷，匈牙利算法还是忘，在复习过一遍之后做出来了

弄清楚匈牙利算法的思路最重要：
1. 找这个点的邻点，如果没有被预定(st==0)则继续
2. 如果这个点没有匹配点或者其匹配点可以找到别的匹配点，则赋值match[a][b]={x,y}，返回1说明找到了
3. 到最后都没有赋值match，即没找到这个点的匹配点，则返回0

和染色法的区别在于：
染色法中间是两个失败条件，做到最后返回1； 匈牙利是中间是成功条件，做到最好返回0

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;

int g[N][N],st[N][N];
typedef pair<int,int> pii;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m;

pii match[N][N];

int find(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<1 || a>n || b<1 ||b>n ||g[a][b]==1) continue;
        if(!st[a][b])
        {
            st[a][b]=1;
            if(match[a][b].first==0 || find(match[a][b].first, match[a][b].second))
            {
                match[a][b]={x,y};
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=1;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]) continue;
            if((i+j)%2) continue;
            memset(st,0,sizeof st);
            if(find(i,j)) cnt++;
        }
    }

    cout<<cnt;
    return 0;
}