匈牙利算法

题目

https://www.luogu.com.cn/problem/P3386

解题过程

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=100010;
struct Node{
    int v;//相邻的边数
    int ne;//指向下一条边 
}e[M];
bool st[N];//表示这个点有没有被访问过 
int n,m,k,idx;
int h[N],match[N]; 
int res;
void Add(int a,int b)
{
    e[++idx]={b,h[a]};
    h[a]=idx;
}
bool dfs(int u)
{
    //开始对其相邻的边进行遍历
    for(int i=h[u];i;i=e[i].ne)
    {
        int v=e[i].v;
        //首先将这个结点判断有没有标记 
        if(st[v])
        {
            continue;
        }
        //还要将其进行标记
        st[v]=true; 
        if(!match[v]||dfs(match[v]))//如果e还没有男盆友或者的男盆友可以换其他女朋友的话
        {
            match[v]=u;
            return 1;   
        } 
    } 
    return 0;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        Add(a,b);//将这两条边进行相连 
    }
    //然后开始遍历每一个点进行运算,如果这里的每一个男结点都满足条件的话，就res++ 
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof(st));
        if(dfs(i))
        {
            res++;
        }
    } 
    cout<<res<<endl;
    return 0;
}