luogu 3386 二分图匹配模板

luogu 3386 二分图匹配模板

​​ 题目背景

二分图

题目描述

给定一个二分图，结点个数分别为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#include#define N 1100inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,next;}data[N*N];int girl[N],n,m,e,h[N];bool used[N];inline bool judge(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (used[y]) continue; used[y]=true; if (!girl[y]||judge(girl[y])){ girl[y]=x; return true; } } return false;}int main(){ freopen("3386.in","r",stdin); n=read();m=read();e=read();int num=0; for (int i=1;i<=e;++i){ int x=read(),y=read();if (y>m) continue; data[++num].y=y;data[num].next=h[x];h[x]=num; } int ans=0; for (int i=1;i<=n;++i){ memset(used,0,sizeof(used)); if(judge(i)) ans++; } printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。