无用的文字
又是一篇笔记，因为不做题的话太容易忘了啊啊啊QAQ看到一个题目知道用什么算法做但就是想不出来的感觉太难受了……
二分图最大匹配
二分图
二分图是指可以被分为两个不相交点子集的图，其中相同点集内无连边。
匈牙利算法
匈牙利算法是用来寻找最大匹配的一个算法。
- 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。
- 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting
path）。
```cpp //匈牙利算法代码实现； //二分图最大匹配；
//即左边的点和右边的点连线最多； //匈牙利算法主要用了增广路径比原路径多;
/因为原路径相当于从左边一点向右匹配，
每次匹配后只有两点两两相配，增广路匹配数+1； 深搜即可 /
#include #include #include
#include #include<ctype.h> using namespace std; int n,m;
const int maxn=233; int a[maxn],mapp[maxn][maxn]; bool vis[maxn]; inline
int read() { int x=0,w=1;char c=getchar(); while(!isdigit(c)){
if(c=='-')w=-1; c=getchar(); }
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return
x*w; } bool match(int x)//x为左侧点标号 { for(int i=1;i<=m;i++)
if(mapp[x][i] and !vis[i]) { vis[i]=1; if(!a[i]||match(a[i])) { a[i]=x;
return true; } } return false; } inline int hungary() { int ans=0;
memset(a,0,sizeof a); for(int i=1;i<=n;i++) { memset(vis,0,sizeof
vis); if(match(i))ans++; } return ans; } int main() { n=read(),m=read();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)mapp[i][j]=read();
printf("%d",hungary()); return 0; }
