APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵)

2018年10月17日 2702点热度 2人点赞 0条评论

洛谷:P3386

题目背景

二分图

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数

输入输出格式

输入格式:

第一行,n,m,e

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边

输出格式:

共一行,二分图最大匹配

输入输出样例

输入样例#1:

1 1 1
1 1

输出样例#1:

1

邻接矩阵(老码风)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int maxn(1005);
int ans;
int n,m,e;
bool vis[maxn][maxn];
bool use[maxn];
int matched[maxn];

inline bool dfs(int);

int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        vis[x][y]=true;
    }
    for(int i=1;i<=n;++i){
        memset(use,false,sizeof use);
        if(dfs(i)) ans++;
    } 
    printf("%d\n",ans);
    return 0;
} 

inline bool dfs(int x){
    for(int i=1;i<=m;++i){
        if(vis[x][i]&&!use[i]){
            use[i]=true;
            if(!matched[i]||dfs(matched[i])){
                matched[i]=x;
                return true;
            }
        }
    }
    return false;
}

邻接矩阵(新码风)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXM = 1e8;
const int MAXN = 1005;

struct node {
	int to,next;
};

node e[MAXM];

bool used[MAXN];
int head[MAXN],cnt,n,m,ee,Ans,Matched[MAXN];

void add(int from,int to) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	head[from] = cnt;
}

inline bool dfs(int u) {
	for(int i = head[u];i;i = e[i].next) {
		int v = e[i].to;
		if(!used[v]) {
			used[v] = true;
			if(!Matched[v] || dfs(Matched[v])) {
				Matched[v] = u;
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> n >> m >> ee;
	for(int i = 1;i <= ee;++i) {
		int from,to;
		cin >> from >> to;
		if(from > n or to > m) continue;
		add(from,to);
	}
	for(int i = 1;i <= n;++i) {
		memset(used,false,sizeof used);
		if(dfs(i)) Ans++;
	}
	cout << Ans << endl;
	return 0;
}

 

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ DFS OI 二分图 二分图匹配 匈牙利算法 图论 模板 洛谷 算法 邻接矩阵 邻接表
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 读 太宰治《人间失格》有感 Google空间(XSpace)自动配置谷歌框架/直连谷歌商店 MongoDB中文全文检索方案 #动漫#《烟花》观后感:莫名其妙的剧情 WPscan扫描Wordpress漏洞的工具使用教程
标签聚合
ST HTML C++ 洛谷 动漫 C/C++ OI 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang