最大匹配問題（匈牙利演算法）

匈牙利演算法（簡單總結）

結束簡單圖論演算法，撒花（哈哈哈）

• 啥是匈牙利演算法
  就是二分圖求最大匹配
  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萌新，舉手敬禮