APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

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

2018年10月17日 1459点热度 1人点赞 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;
}

 

 

标签: C/C++ C++ DFS OI 二分图 二分图匹配 匈牙利算法 图论 模板 洛谷 算法 邻接矩阵 邻接表
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
关于P站(Pixiv)的搜索姿势 #C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵) Linux中zip/unzip命令简略笔记 中行天依小柠檬借记卡已收到 人的一生都在治愈自己的童年 #置頂#已購漫畫/輕小說匯總整理
标签聚合
日常 C++ 动漫 OI 洛谷 ST HTML C/C++
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang