欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——模板复习13

程序员文章站 2024-01-14 13:58:28
...

这里只有模板,并不作讲解,仅为路过的各位做一个参考以及用做自己复习的资料,转载注明出处。

二分图匹配

匈牙利算法

/*Copyright: Copyright (c) 2018
*Created on 2018-11-02  
*Author: 十甫
*Version 1.0 
*Title: 匈牙利算法
*Time: inf mins
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10005;
const int maxm = 100005;

int to[maxn][maxn], n, m, e;
int matchx[maxn], matchy[maxn];
bool vis[maxn];
bool dfs(int u) {
    for(int v = n + 1;v <= n + m;v++) if(to[u][v]) {
        if(vis[v]) continue;
        vis[v] = true;
        if(!matchy[v] || dfs(matchy[v])) {
            matchx[u] = v, matchy[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d", &n, &m, &e);
    for(int i = 1;i <= e;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if(a < 1 || a > n || b < 1 || b > m) continue;
        to[a][b + n] = to[b + n][a] = true;
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) {
        if(!matchx[i]) {
            memset(vis, false, sizeof(vis));
            ans += dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

 

相关标签: 二分图匹配