二分图

野性酷女 2021-12-03 17:34 244阅读 0赞

# About二分图 #

[参考博客 by ling\_wang][by ling_wang]  
[参考博客 by Matrix67][by Matrix67]

# 模板题 luogu3386 #

[luogu3386 二分图匹配 の 传送门][luogu3386 _ _]

这里是 **匈牙利算法**  
Code

#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int N = 1007, M = 1007; int n, m, e, cnt, ans, nxt[N * M], to[N * M], head[N], ch[1010]; bool vis[1010]; inline int read(){ int ans = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') ans = (ans << 3) + (ans << 1) + ch - 48, ch = getchar(); return ans * f; } void add(int u, int v){ nxt[++cnt] = head[u]; to[cnt] = v; head[u] = cnt; } bool dfs(int k){ for (int i = head[k]; i; i = nxt[i]){ int v = to[i]; if (!vis[v]){ vis[v] = true; if (!ch[v] || dfs(ch[v])){ ch[v] = k; return true; } } } return false; } int main(){ //freopen("testdata.in.txt", "r", stdin); n = read(), m = read(), e = read();; for (int i = 1; i <= e; ++i){ int x = read(), y = read(); if (x <= n && y <= m) add(x, y); } ans = 0; for (int i = 1; i <= n; i++){ memset(vis, false, sizeof(vis)); if (dfs(i)) ans++; //else printf("%d\n", i); } printf("%d\n", ans); return 0; }

转载于:https://www.cnblogs.com/DorkyTAT/p/11160706.html

[by ling_wang]: https://blog.csdn.net/ling_wang/article/details/79830980
[by Matrix67]: http://www.matrix67.com/blog/archives/116
[luogu3386 _ _]: https://www.luogu.org/problemnew/show/P3386

发表评论取消回复

表情：

评论列表（有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_二分图_中等_785. 判断二分图

目录 1.题目 2.思路 3.代码实现（Java） 1.题目存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1

左手的ㄟ右手/ 2023年10月06日 22:37/ 0 赞/ 36 阅读

相关二分图匹配

Bi-partite graph ![20130902222653718][] 二分图的定义：二分图是这样的一个图，它的顶点可以分为两个集合X和Y。所有的边关联

迷南。/ 2022年12月19日 03:38/ 0 赞/ 159 阅读

相关二分图（Java）

//对于节点数目不同可以处理， //Java语言实现，最基础未优化 public class ErFenTu { p

快来打我*/ 2022年08月21日 02:28/ 0 赞/ 129 阅读

相关二分图匹配

今天看了很多博客！终于看懂了一点点，想记录一下！首先你要知道什么是增广路径（虽然我现在还不明白![大哭][wail.gif]）这是一种用增广路求二分图最

秒速五厘米/ 2022年08月01日 03:11/ 0 赞/ 169 阅读

相关二分图匹配

[二分图最大匹配问题匈牙利算法][Link 1] [二分图最大匹配的König定理及其证明][K_nig] [Link 1]: http://www.matrix67.

客官°小女子只卖身不卖艺/ 2022年06月13日 07:49/ 0 赞/ 149 阅读

相关二分图

二分图的一个等价定义是：不含有「奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。 ![Center][] 简而言之，就是顶

矫情吗；*/ 2022年06月09日 13:53/ 0 赞/ 172 阅读

相关二分图一?二分图判定(不连通的)

1121 : 二分图一?二分图判定时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述大家好，我是小Hi和小Ho的小伙伴N

以你之姓@/ 2022年06月08日 01:24/ 0 赞/ 225 阅读

相关 BZOJ 4025: 二分图

BZOJ 4025: 二分图这个题嘛，分治线段树可以做啦…但是我并不想写…毕竟并查集还不能路径压缩只能按质合并…所以，我觉得还是写LCT比较友善… LCT维护最晚删除

灰太狼/ 2021年12月23日 03:49/ 0 赞/ 216 阅读

相关二分图匹配

该文章是从https://blog.csdn.net/qq\_41730082/article/details/81162561复制过来的二分图匹配，自然要先从定义入手，那

￡神魔★判官ぃ/ 2021年12月11日 13:37/ 0 赞/ 523 阅读

相关二分图

About二分图 [参考博客 by ling\_wang][by ling_wang] [参考博客 by Matrix67][by Matrix67] 模板题 l

野性酷女/ 2021年12月03日 17:34/ 0 赞/ 245 阅读