匈牙利算法:
算法描述:
如果你想找的妹子已经有了男朋友,
你就去问问她男朋友,
你有没有备胎,
把这个让给我好吧
多么真实而实用的算法
TIP: 因为你要去问的都是男孩子,所以存边的时候,都是由男孩子指向女孩子
//来自算法基础课
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<string>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 1e5+5;
int n1,n2,m,ans,cnt,first[N];//已知二分图,左侧集合个数为n1,右侧个数为n2
int match[N];//记录已有配对情况
bool vis[N];//判重
struct edge {
int end,nxt;
} bian[N<<2];
void addedge(int s,int e) {
cnt++;
bian[cnt].end = e;
bian[cnt].nxt = first[s];
first[s] = cnt;
}
bool find(int s) {
for(register int i=first[s]; i!=0; i=bian[i].nxt) {
int e = bian[i].end;
if(!vis[e]){
vis[e] = 1;
if(match[e]==0 || find(match[e])) {
match[e] = s;
return true;
}
}
}
return false;
}
int main(){
read(n1),read(n2),read(m);
while(m--) {
int a,b;
read(a),read(b);
addedge(a,b);
}
for(register int i=1; i<=n1; i++) {
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}
printf("%d\n",ans);
}
/
彩蛋:
一定要记得尝试
错过要比错误难受一百倍
/
印象深刻
愿天下有情人皆被green(FFF.jpg)
图论一刷 自己在csdn上写了一下二分图查找最大匹配的博文
如果st数组看不懂或者啥的可以去看看,交流交流也行
https://blog.csdn.net/WJPnb1/article/details/126332263
善良的牛头人
人生导师yxc~~
颜值主播在线教学 交友课程
对对对,笑死我了当时,还有那个贼真实的绿色边