二分图匹配

Author Avatar
Llf0703 4月 21, 2018
  • 在其它设备中阅读本文章

我是看这篇学懂的,真的写得很好,所以我就不在这里总结了,只发个模板

https://blog.csdn.net/dark_scope/article/details/8880547

模板题:洛谷 P3386【模板】二分图匹配

#include<bits/stdc++.h>
using namespace std;
bool edge[1005][1005];
bool used[1005];
int mch[1005];
int n,m,e,a,b,c,ans;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9') 
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
bool find(int x)
{
    for (int i=1;i<=m;i++)
        if (!used[i] && edge[x][i])
        {
            used[i]=true;
            if (!mch[i] || find(mch[i]))
            {
                mch[i]=x;
                return true;
            }
        }
    return false;
}
int main()
{
    memset(edge,false,sizeof(edge));
    n=read();m=read();e=read();
    for (int i=1;i<=e;i++)
    {
        int u=read(),v=read();
        if (v>m) continue;
        edge[u][v]=true;
    }
    for (int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        ans+=find(i);
    }
    printf("%d",ans);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.

本文链接:https://llf0703.com/p/bipartite-matching.html