P3386 【模板】二分图匹配(匈牙利算法)

题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1： 

1 1 1

1 1

输出样例#1： 

1

说明

n,m \leq 1000n,m≤1000 ， 1 \leq u \leq n1≤u≤n ， 1 \leq v \leq m1≤v≤m

因为数据有坑，可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。

算法：二分图匹配

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=1e3+;

const int M=5e5+;

int n,m,e,ans;

int head[N],num_edge;

struct Edge

{

    int u,v,nxt;

}edge[M];

int match[N];

int visited[N],tim;

inline int read()

{

    char c=getchar();int num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

inline void add_edge(int u,int v)

{

    edge[++num_edge].u=u;

    edge[num_edge].v=v;

    edge[num_edge].nxt=head[u];

    head[u]=num_edge;

}

int dfs(int u)

{

    for(int i=head[u],v;i;i=edge[i].nxt)

    {

        v=edge[i].v;

        if(visited[v]==tim)

            continue;

        visited[v]=tim;

        if(!match[v]||dfs(match[v]))

        {

            match[v]=u;

            return ;

        }

    }

    return ;

}

int main()

{

    //freopen("testdata.in","r",stdin);

    n=read(),m=read(),e=read();

    for(int i=,u,v;i<=e;++i)

    {

        u=read(),v=read();

        if(u>n||v>m)

            continue;

        add_edge(u,v);

    }

    for(int i=;i<=n;++i)

    {

        ++tim;

        ans+=dfs(i);

    }

    printf("%d",ans);

    return ;

}