匈牙利算法（简单总结）

结束简单图论算法，撒花（哈哈哈）

• 啥是匈牙利算法
  就是二分图求最大匹配
  1 将所有点分为两个阵营（阵营里没有连线，只能和对方阵营连线）
  2 求最大的一一对映数是多少
• 现在有 编号1，2，3，4个男同胞和1，2，3，4个女同胞
  他们之间有互相暗恋的对象（有的还喜欢好几个）
  我们就是月老进行红线牵，来能牵出多少对（保证一男一女）

  来个通俗版本

这时匈牙利算法就可以当作月老专用算法
1 先选一个阵营
2 进行连线，如果有人，这看他的伴侣，能不能换一个成立，就换
3 以此类推 ， 得最大匹配数
模板
一定不要背，理解就可以打出来，不需要硬背，我反正都是理解记忆

int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 bool find(int x) { 
    for (int i = h[x]; i != -1; i = ne[i]) { 
    int j = e[i]; if (!st[j]) { 
    st[j] = true; if (match[j] == 0 || find(match[j])) { 
    match[j] = x; return true; } } } return false; } // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1; i ++ ) { 
    memset(st, false, sizeof st); if (find(i)) res ++ ; } 

肯定很抽象，没关系（代码很简单）
hdu一道月老题（模板题），看看吧，哈哈
->过山车
代码

讯享网#include<iostream> #include<cstring> using namespace std; const int N=510; int n,m,k; int h[N],e[N*2],ne[N*2],idx; bool st[N]; int cut[N]; void add(int a,int b){ 
    e[idx]=b;ne[idx]=h[a];h[a]=idx++; } bool find(int x){ 
    for(int i=h[x];~i;i=ne[i]){ 
    int j=e[i]; if(!st[j]){ 
    st[j]=true; if(!cut[j]||find(cut[j])){ 
    cut[j]=x; return true; } } } return false; } int main(){ 
    while(cin>>k,k){ 
    cin>>n>>m; memset(h,-1,sizeof h);idx=0; memset(cut,0,sizeof cut); for(;k;k--){ 
    int a,b; scanf("%d%d",&a,&b); add(a,b); } int ans=0; for(int i=1;i<=n;i++){ 
    if(find(i)){ 
    ans++; memset(st,0,sizeof st); } } cout<<ans<<endl; } return 0; } 

还有一道模板题
P2071 座位安排
代码

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N=8010; int h[N],e[N*2],ne[N*2],idx; int macth[N]; bool st[N]; int n; void add(int a,int b){ 
    e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool find(int x){ 
    for(int i=h[x];~i;i=ne[i]){ 
    int j=e[i]; if(!st[j]){ 
    st[j]=true; if(!macth[j]||find(macth[j])){ 
    macth[j]=x; return true; } } } return false; } int main(){ 
    cin>>n; memset(h,-1,sizeof h); for(int i=1;i<=2*n;i++){ 
    int a,b; scanf("%d%d",&a,&b); add(i,a); add(i,a+n); add(i,b); add(i,b+n); } int ans=0; for(int i=1;i<=2*n;i++){ 
    memset(st,0,sizeof st); if(find(i)) ans++; } cout<<ans; return 0; } 

再来一道抽像的最大匹配问题

讯享网

棋盘覆盖

代码

讯享网#include<iostream> #include<algorithm> #include<cstring> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N=110; PII cut[N][N]; bool g[N][N]; bool st[N][N]; int n,m; int fx[]={ 
   -1,0,1,0},fy[]={ 
   0,1,0,-1}; int find(int xx,int yy){ 
    for(int i=0;i<4;i++){ 
    int u=xx+fx[i],v=yy+fy[i]; if(!st[u][v]&&!g[u][v]&&u&&v&&v<=n&&u<=n){ 
    st[u][v]=true; if(!cut[u][v].x||find(cut[u][v].x,cut[u][v].y)){ 
    cut[u][v]={ 
   xx,yy}; return true; } } } return false; } int main(){ 
    cin>>n>>m; for(;m;m--){ 
    int a,b; scanf("%d%d",&a,&b); g[a][b]=true; } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((i+j)&1&&!g[i][j]){ 
    if(find(i,j)) ans++; memset(st,0,sizeof st); } cout<<ans; return 0; } 

详细解析可以看链接的题解，我比较懒

代码

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=210; bool g[N][N]; bool st[N]; int cut[N]; int n,m,t; bool find(int u){ 
    for(int i=1;i<=m;i++){ 
    if(!st[i]&&!g[u][i]){ 
    st[i]=true; if(!cut[i]||find(cut[i])){ 
    cut[i]=u; return true; } } } return false; } int main(){ 
    cin>>n>>m>>t; for(;t;t--){ 
    int x,y; scanf("%d%d",&x,&y); g[x][y]=true; } int ans=0; for(int i=1;i<=n;i++){ 
    memset(st,0,sizeof st); if(find(i)) ans++; } cout<<ans; return 0; } 

就这么多吧，最大匹配问题模板不会难，在于怎么转换问题
qwq萌新，举手敬礼