二分图最大匹配——POJ 1469

2024-09-05 04:18
文章标签 二分 最大 匹配 poj 1469

本文主要是介绍二分图最大匹配——POJ 1469,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对应POJ题目:点击打开链接


COURSES
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17976 Accepted: 7086

Description

Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions: 

  • every student in the committee represents a different course (a student can represent a course if he/she visits that course) 
  • each course has a representative in the committee 

Input

Your program should read sets of data from the std input. The first line of the input contains the number of the data sets. Each data set is presented in the following format: 

P N 
Count1 Student 1 1 Student 1 2 ... Student 1 Count1 
Count2 Student 2 1 Student 2 2 ... Student 2 Count2 
... 
CountP Student P 1 Student P 2 ... Student P CountP 

The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses �from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you抣l find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N. 
There are no blank lines between consecutive sets of data. Input data are correct. 

Output

The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.

Sample Input

2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1

Sample Output

YES
NO

Source


题意:有P门课和N个学生,一个学生可以选0~p门课,问是否有一个集合包含P个学生,使得该集合里每个学生分别对应P门课,即每门可都有学生对应

思路:二分图求最大匹配模板,就是用个net[i][j]数组,i表示第i门课程,j表示学生ID。这里用DFS和BFS


DFS

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define ms(x,y) memset(x,y,sizeof(x))
const int MAXN=300+10;
const int INF=1<<30;
using namespace std;
int link[MAXN];
int vis[MAXN];
int net[MAXN][MAXN];
int left,right;
int c,n;int dfs(int u)
{for(int v=1; v<=n; v++){if(!vis[v] && net[u][v]){vis[v] = 1;if(link[v] == -1 || dfs(link[v])){link[v] = u;return 1;}}}return 0;
}int MaxMatch()
{int num=0;ms(link, -1);for(int i=1; i<=c; i++){ms(vis, 0);if(dfs(i)) num++;}return num;
}int main()
{//freopen("in.txt","r",stdin);int T;scanf("%d", &T);while(T--){ms(net,0);scanf("%d%d", &c,&n);if(n < c){printf("NO\n");continue;}for(int i=1; i<=c; i++){int t,m;scanf("%d", &t);for(int j=0; j<t; j++){scanf("%d", &m);net[i][m] = 1;}}int ans = MaxMatch();if(ans == c) printf("YES\n");else printf("NO\n");}return 0;
}



BFS


#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define ms(x,y) memset(x,y,sizeof(x))
const int MAXN=300+10;
const int INF=1<<30;
using namespace std;
int link_l[MAXN];
int link_r[MAXN];
int vis[MAXN];
int pre[MAXN];
int net[MAXN][MAXN];
int c,n;int MaxMatch()
{ms(link_l, -1);ms(link_r, -1);int res = 0;for(int i=1; i<=c; i++){//以左边(即课程)为起点寻找一条增广路ms(vis, 0);//清空标记ms(pre, 0);//清空前驱queue<int>q;q.push(i);int ok=0;while(!q.empty()){int u = q.front();q.pop();for(int v=1; v<=n; v++){if(!vis[v] && net[u][v]){//在右边(即学生)寻找vis[v] = 1;if(link_l[v] == -1){//该点还没有匹配ok = 1;int l = u, r = v;while(l)//利用前驱反转路径{int tmp = link_r[l];link_l[r] = l;link_r[l] = r;l = pre[l];r = tmp;}break;//已经找到增广路,退出}else{//该点已经匹配pre[link_l[v]] = u;//记录前驱q.push(link_l[v]);//继续寻找}}}if(ok) break;//已经找到增广路,退出}if(ok) res++;//有增广路,总值加1}return res;
}int main()
{//freopen("in.txt","r",stdin);int T;scanf("%d", &T);while(T--){ms(net,0);scanf("%d%d", &c,&n);if(n < c){printf("NO\n");continue;}for(int i=1; i<=c; i++){int t,m;scanf("%d", &t);for(int j=0; j<t; j++){scanf("%d", &m);net[i][m] = 1;}}int ans = MaxMatch();if(ans == c) printf("YES\n");else printf("NO\n");}return 0;
}



这篇关于二分图最大匹配——POJ 1469的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137926

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制