//形象:男的女的互有好感,现在为男的(a)找女朋友(b)且保证没有脚踏多只船 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=1e5+10; int e[N],h[N],ne[N],mat[N],idx; bool st[N]; int n1,n2,m,res; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool find(int k) { for(int i=h[k];i!=-1;i=ne[i]) { int j=e[i]; if(!st[j]) { st[j]=true; if(mat[j]==0||find(mat[j]))//如果这个b还没被匹配,或者能为已经配备的mat[j]找到下家,就成功为k匹配 { mat[j]=k; return true; } } } return false; } int main(void) { cin>>n1>>n2>>m; memset(h,-1,sizeof h); while(m--) { int a,b; cin>>a>>b; add(a,b); //只为a找b所以只存一个方向就行 } for(int i=1;i<=n1;i++) { memset(st,false,sizeof st); if(find(i))res++; } cout<<res<<endl; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:759 |
C语言训练-排序问题<1> (C语言代码)浏览:1395 |
简单的a+b (C语言代码)浏览:554 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:830 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:515 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:645 |
Hello, world! (C语言代码)浏览:910 |
永远的丰碑 (C语言代码)浏览:598 |
C语言程序设计教程(第三版)课后习题10.7 (用指针求解)浏览:1526 |
拆分位数 (C语言代码)浏览:550 |