匈牙利算法

染色法判断二分图

染色法判断二分图的原理：二分图中不存在奇数环（节点数为奇数的环），因此图中相邻两点颜色均应该不同。可以用此方法来判断二分图。
模板题目：https://www.acwing.com/problem/content/862/
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+5;
vector<vector<int>>gra(N,vector<int>());
vector<int>color(N,0);
int m,n,v,u;
bool dfs(int u,int c)
{
    color[u] = c;
    for(int&v:gra[u])//对所有相邻节点进行染色
    {
        if(!color[v])//若没被染色
        {
            if(!dfs(v,3-c))return false;//递归染上不同的颜色
        }
        else
        {
            if(color[v]!=3-c)//若已被染色，则判断是否颜色不同。
            {
                return false;
            }
        }
    }
    return true;
}
int main(void)
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        gra[u].push_back(v);//无向图
        gra[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                printf("No");
                return 0;
            }
        }
    }
    printf("Yes");   
}

匈牙利算法

匈牙利算法用来求二分图的最大匹配。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
模板题目：https://www.acwing.com/problem/content/description/863/
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =1001;
int n1,n2,m,u,v;
vector<vector<int>>gra(N,vector<int>());
vector<bool>vis;
vector<int>match(N,0);
bool find(int x)
{
    for(int&v:gra[x])//遍历所有可能匹配的点
    {
        if(!vis[v])//如果另一方还没有被考虑
        {
            vis[v]=true;
            if(match[v]==0 || find(match[v]))//若另一方没有匹配对象或者其匹配对象能够更换成另外的匹配对像
            {
                match[v] =x;//匹配成功
                return true;
            }
        }
    }
    return false;
}
int main(void)
{
    scanf("%d%d%d",&n1,&n2,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        gra[u].push_back(v);//只加入一边，当成有向图
    }
    int res=0;
    for(int i=1;i<=n1;i++)
    {
        vis = vector<bool>(n2,false);//每次重置，所有另一方被考虑的状态。
        if(find(i)) ++res;
    }
    printf("%d",res);
}