NYOJ239 月老的难题 【二分图最大匹配·匈牙利】
amp 最大 匹配 二分 难题 183 匈牙利
2023-09-11 14:14:44 时间
月老的难题
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描写叙述
-
月老准备给n个女孩与n个男孩牵红线。成就一对对美好的姻缘。
如今,因为一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。
如今已知哪些男孩与哪些女孩假设结婚的话。能够结成幸福的家庭。月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。
如果男孩们分别编号为1~n,女孩们也分别编号为1~n。
#include <stdio.h> #include <string.h> #define maxn 505 #define maxm 10010 int n, k, id; int head[maxn], B[maxn]; bool vis[maxn]; struct Node { int v, next; } E[maxm]; void addEdge(int u, int v) { E[id].v = v; E[id].next = head[u]; head[u] = id++; } bool findPath(int x) { int i, v; for(i = head[x]; i != -1; i = E[i].next) { v = E[i].v; if(!vis[v]) { vis[v] = true; if(!B[v] || findPath(B[v])) { B[v] = x; return true; } } } return false; } int MaxMatch() { int ans = 0; for(int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(bool) * (n + 1)); if(findPath(i)) ++ans; } return ans; } int main() { // freopen("stdin.txt", "r", stdin); int t, u, v; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &k); memset(head, -1, sizeof(int) * (n + 1)); memset(B, 0, sizeof(int) * (n + 1)); id = 0; while(k--) { scanf("%d%d", &u, &v); addEdge(u, v); } printf("%d\n", MaxMatch()); } return 0; }
相关文章
- Lintcode: Nuts & Bolts Problem
- Leetcode: Water and Jug Problem && Summary: GCD求法(辗转相除法 or Euclidean algorithm)
- UVALive3938 "Ray, Pass me the dishes!" 线段树动态区间最大和
- QT高级编程技巧(一)-- 编写高效的signal & slot通信代码
- c编程:求出4×4矩阵中最大和最小元素值及其所在行下标和列下标,求出两条主对角线元素之和。
- BEGINNING SHAREPOINT® 2013 DEVELOPMENT 第13章节--使用业务连接服务创建业务线解决方式 创建启用BCS的业务解决方式
- mother's day.py 母亲节
- 写出 && 和 & 的区别。
- 复盘:Python内存管理&垃圾回收原理
- 【C位运算&基础+面试题】位运算中阶详解及面试题
- UVaLive 6585 && Gym 100299F Draughts (暴力+回溯)
- 使用 Rust & Warp 和 Docker 构建安全的 WebSocket 服务器
- 经典线程同步问题(生产者&消费者)--Java实现
- React生产环境打包&&后台环境运行(有跨域+无跨域)
- ModuleNotFoundError: No module named ´sklearn.utils.linear_assignment_´
- Cocos2d-x MultipleTouch & CCControllButton's confusion
- 我的Android进阶之旅------>解决:Execution failed for task ':app:transformResourcesWithMergeJavaResForDebug'.
- AT&T联盟Ubuntu,开放网络大步走
- 学习笔记(30):Python网络编程&并发编程-Event事件
- 【Unity入门计划】制作RubyAdventure02-处理瓦片地图&碰撞
- c#集合_键值对Dictionary & SortedList
- Java的流程控制(选择结构语句 if ~ switch &循环结构语句dowhile ~ for)