---
title: 二分圖最大匹配與匈牙利演算法
tags: 7th 教學
slideOptions:
theme: black
transition: 'slide'
---
# 二分圖最大匹配與匈牙利演算法
#### Author:H1de_on_bruH

## 何謂二分圖?
試想一個情境
學校裡有很多男生跟女生，他們各自有一些喜歡的對象
而到了歲末舞會，這些男女們就會開始湊成一對一對的
當然這些人中不乏一些渣男渣女，表面上跟你很好，實際上有很多對象
但你是校長，你才不管有哪些人沒有伴，你只在乎最多可以湊出多少對

那調查完所有人喜歡的對象後，我們可以畫出像上方的一張圖，學術上稱之為二分圖
所謂二分圖就是你可以把這個圖的節點分成兩個集合，同個集合內的點不直接相連

現在你關心的最多有幾對，就可以被轉化成二分圖最大匹配

## 匈牙利演算法
我們從A開始看，他和a,b都有一些"良好"的關係
所以我們暫時把A跟a湊成一對

接下來看到B，他只跟c有曖昧，所以我們就把他們湊一對

最後我們看到C，他只跟a有關係，但此時A跟a已經湊一對了
那一般我們會試著打斷配對，重新配配看，也就是說把C跟a配一對後，讓A再去找一次

於是我們回到A，A跟a,b有關係，因為剛剛就已經知道為甚麼A不能跟a配了，現在連智障都可以很清楚的告訴你，我們現在只能讓A跟b配對

只不過我們要怎麼樣寫出程式讓電腦合理推測我們A接下來要跟誰配呢?

那我們就是測試看看A跟a配之後，C能不能再配
如果可以C就放掉
那不行的話A就只能再考慮其他的對象，於是輪到b
發現b沒有配到對像，所以就直接配下去


$於是乎，我們就找到最多的配對數了_{めでたしめでたし}$

## 最小點覆蓋
最小點覆蓋數的意思就是，我們最少要選多少個點，才可以把所有的邊的其中一點都給覆蓋住?
如果你想跳過嚴謹的證明，那我們可以直接看結論，也就是
>最小點覆蓋數=最大匹配數
> ----König定理

那詳細的證明請參見下方連結 ~~因為筆者本人也只有背結論不知道怎麼證明~~
www.matrix67.com/blog/archives/116

## 例題
### [TIOJ#1253](https://tioj.ck.tp.edu.tw/problems/1253)
經典的匈牙利演算法裸題
我們先這樣建模:
>假設(i,j)上有隻皮皮，那我們就在圖上讓i點連到j點
>這樣可以弄出一個二分圖，我們要求用的最少次數就會是這2N個點的最小點覆蓋

可以利用König定理把最小點覆蓋數轉換成最大匹配數
這樣我們就可以輕鬆的AC這題

甚麼?你不會實作匈牙利?那就點下面的箱子學學這個神奇的東西吧
:::spoiler 點我看實作

//TIOJ#1253
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,m,path[N][N],p[N],vis[N];
bool match(int now)
{
     for(int i=n;i<=2*n;i++)
     {
          if(path[now][i]&&vis[i]==0)
          {
               vis[i]=1;
               if(p[i]==0||match(p[i]))
               {
                    p[i]=now;
                    return true;
               }
          }
     }
     return false;
}
int hungarian()
{
     int ans=0;
     for(int i=1;i<=n;i++)
     {
          memset(vis,0,sizeof(vis));
          if(match(i))ans++;
     }
     return ans;
}
int counter;
void solve()
{
     for(int i=1;i<=n;i++)for(int j=n+1;i<=2*n;i++)path[i][j]=p[i]=p[j]=0;
     for(int i=0;i<m;i++)
     {
          int a,b;cin>>a>>b;
          path[a][b+n]=1;
          path[b+n][a]=1;
     }
     cout<<"Case #"<<++counter<<":";
     cout<<hungarian()<<endl;
}
signed main()
{
    while(cin>>n>>m&&n&&m)solve();
}

:::

---
### [洛谷P2756](https://www.luogu.com.cn/problem/P2756)
比上面更裸的題目，這次是要求出最大的配對方法，那只要把i跟p[i]成對輸出就可以解了
:::spoiler 點我看解
https://www.luogu.com.cn/record/63994967
:::

## Outline:[網路流建模](https://www.youtube.com/watch?v=u4dw3KuTz5s&t=108s)

:::spoiler 本篇的夕張
哈密哈>\\\\\\\<
:::