首页 > 其他 > 详细

P3386 【模板】二分图匹配

时间:2020-02-28 13:40:54      阅读:47      评论:0      收藏:0      [点我收藏+]

https://www.luogu.com.cn/problem/P3386

 

技术分享图片
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n,m,e,link[maxn][maxn],ans;
int used[maxn],girl[maxn];
int find(int x){
    for(int j = 1; j <= m; j++){
        //used[j]=1说明有标记,试图改变这个妹子归属问题但是没有成功
        if(link[x][j] && !used[j]) {
            used[j] = 1;
            if (!girl[j] || find(girl[j])) {
                //名花无主或者能腾出地方来
                girl[j] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin >> n >> m >> e;
    for(int i = 0; i < e; i++){
        int u,v;
        cin >> u >> v;
        if(u > n || v > m)
            continue;
        link[u][v] = 1;
    }
    for(int i = 1; i <= n; i++){
        memset(used,0, sizeof(used));
        if(find(i))
            ans++;
    }
    cout << ans;
    return 0;
}
View Code

 

匈牙利算法,即由增广路求最大匹配

大佬的博客

https://blog.csdn.net/dark_scope/article/details/8880547

P3386 【模板】二分图匹配

原文:https://www.cnblogs.com/xcfxcf/p/12376602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!