二分图最大匹配——匈牙利算法

Powered by:NEFU AB_IN

所谓匹配就是左右集合的点连起来。

显然这个最大的匹配数为：$3$

先给出主要函数

bool vis[N];
int match[N];
bool dfs(int u)
{
    for(int i = h[u]; ~i; i = e[i].ne){
        int v = e[i].v;
        if(!vis[v]){
            vis[v] = true;
            if(!match[v] || dfs(match[v])){
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}eturn 0;
}

• 用链式前向星存图，$dfs$的循环就是遍历包含$u$的边。$u$在左集合里。
• $vis$记录这个点（右集合里）有没有以前走过。
• 如果没走过，那么就标记上走过。$lk$是以右集合的点为下标，值为左集合的点，$lk[v]=u$证明$u$和$v$连上了。
• 下一个$if$
  • 如果这个$v$没有被用，那么直接赋值。
  • 或者看看这个$v$对应的已匹配$u$能不能再找一个别的$v$匹配。如果可以，那么这两个$u$都可以匹配上两个不同的$v$。

再给出两个重要结论：

最小顶点覆盖 = 二分图的最大匹配。

最大独立集 = 点的总数 - 最小顶点覆盖。

顶点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
独立集：是一个点集，点集中的各点之间没有连边。

POJ1274 The Perfect Stall

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=100010;
struct Edge
{
    int u, v, next;
}edge[maxn<<2];
int head[maxn];
int cnt;
void add_edge(int u, int v)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int n,m,t,x,y;
int flag;
bool vis[maxn];
int lk[maxn];
bool dfs(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(!vis[v]){
            vis[v]=1;
            if(!lk[v] || (dfs(lk[v]))){
                lk[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    IOS;
    while(cin>>n>>m){
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++){
            cin>>t;
            while(t--){
                cin>>x;
                add_edge(i,x);//有向图
            }
        }
        memset(lk,0,sizeof(lk));
        int ans=0;
        for(int i=1;i<=n;i++){//遍历每一个左集合点
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

POJ1325 Machine Schedule

题目要求使机器重启的次数要尽量少，又要把所有的任务都执行完，也就可以把题目转换成最小顶点覆盖，根据二分图的性质：最小顶点覆盖=最大匹配数。
值得注意的一点是开始状态为0，所以那些模式为0的边不要加

/*
 * @Description: file content
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-08-13 02:40:20
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-08-13 02:48:35
 */
#include<iostream>
#include<vector>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<stack>
using namespace std;
#define LL                          long long
#define ULL                         unsigned long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;

const int N = 1e6 + 10;
struct Edge
{
    int u, v, w, next;
}edge[N << 2];
int head[N];
int cnt;
void add_edge(int u, int v, int w)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    memset(head, -1, sizeof(head));
    cnt = 0;
}
bool vis[N];
int lk[N];
bool dfs(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].v;
        if(!vis[v]){
            vis[v] = 1;
            if(!lk[v] || (dfs(lk[v])) ){
                lk[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    IOS;
    int n, m, k, x, y;
    while(cin >> n){
        init();
        if(n == 0) break;
        cin >> m >> k;
        for(int i = 0; i < k; ++ i){
            cin >> i >> x >> y;
            if(!x || !y) continue;
            add_edge(x, y, 1);
        }
        memset(lk, 0, sizeof(lk));
        int ans = 0;
        for(int i = 1; i <= n; ++ i){
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) ans ++;
        }
        cout << ans << '\n';
    }
    return 0;
}