APTX博客

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

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

2018年10月17日 2652点热度 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 章 直哉与蓝对话
#C/C++#数据结构:ST表模板 KikoPlay:开源的全功能弹幕播放器(动漫推荐) 《从零》第二季&《春物》第三季制作决定 小米手环4NFC复制学校加密MifareClassic卡尝试与过程 #动漫#《学园孤岛》OP/ED/角色歌下载 Linux下使用Sublime Text3 破解汉化并配置C++编程环境
标签聚合
HTML 洛谷 ST C++ OI 动漫 日常 C/C++
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang