POJ1469_COURSES(二部图最大匹配)

POJ1469_COURSES(二部图最大匹配)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

解决报告

http://blog.csdn.net/juncoder/article/details/38136065

题目传送门

题意:

n个学生p门课程,每一个学生学习0或1以上的课程。

问:能否够组成委员会。满足

每一个学生代表一门不同的课程

一门课程在委员会中有一名代表

思路:

非常明显的二分图的完备匹配。

#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 330
#define P 110
using namespace std;
int mmap[N+P][N+P],n,p,pre[N+P],vis[N+P],m,k;
int dfs(int x)
{
    for(int i=p+1;i<=p+n;i++)
    {
        if(!vis[i]&&mmap[x][i])
        {
            vis[i]=1;
            if(pre[i]==-1||dfs(pre[i]))
            {
                pre[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            memset(mmap,0,sizeof(mmap));
            memset(pre,-1,sizeof(pre));
            scanf("%d%d",&p,&n);
            for(i=1;i<=p;i++)
            {
                scanf("%d",&m);
                for(j=1;j<=m;j++)
                {
                    scanf("%d",&k);
                    mmap[i][k+p]=1;
                }
            }
            int ans=0;
            for(i=1;i<=p;i++)
            {
                memset(vis,0,sizeof(vis));
                ans+=dfs(i);
            }
            if(ans==p)
            printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

COURSES
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 17166   Accepted: 6748

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/116823.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 低延迟视频传输_网络延时

    低延迟视频传输_网络延时微信后台如何应对像跨年,特殊时刻(比如2022年2月22日22时22分22秒)这样的朋友圈突发流量,可做如下策略(只是比如):优先让发一张图片的成功。九宫格只成功一部分,剩余的强有损压缩。朋友多的优先成功。(也可以反过来)设置三天可见的优先成功。(也可以反过来)年轻女性优先成功。(这个没毛病)历史点赞多的优先成功。(也可以反过来)头像穿西装打领带的经理统统失败。…在不影响P99用户体验的前提下,提供有损服务,保证核心可用性,这就是柔性。但数据传输的思维定势并不认可柔性。受TCP的影

    2022年10月3日
    2
  • notepad++正则表达式替换字符串

    notepad++正则表达式替换字符串则表达式是一个查询的字符串,它包含一般的字符和一些特殊的字符,特殊字符可以扩展查找字符串的能力,正则表达式在查找和替换字符串的作用不可忽视,它能很好提高工作效率。EditPlus的查找,替换,文件中查找支持以下的正则表达式:表达式说明/t制表符./n新行..匹配任意字符.|匹配表达式左边和右边的字符.例如,”ab|bc”匹配”ab”或者”bc”….

    2022年5月17日
    43
  • 推荐几个免费看动漫的网站

    推荐几个免费看动漫的网站相信很多喜欢看动漫的网友都有过想看番却找不到资源的经历,尤其是刚入宅的萌新,想看却又看不到的感觉很痛苦把,那么今天就给大家介绍几个好用的追番网站。1.bilibibilibili是国内知名的视频弹幕网站,这里有最及时的动漫新番,最棒的ACG氛围,最有创意的Up主。2.樱花动漫:种类很全,基本都没有圣光,很多人都喜欢用这个网站看番,非常nice3.bimibimi:M站4.zzzfuu:z站,种类很全:5.m.qixu8.cn一款手机端在线追番的网……

    2022年7月18日
    63
  • Android—Gradle教程(一)「建议收藏」

    Android—Gradle教程(一)「建议收藏」前言在前几篇中,讲解了Groovy的基础语法,学习新语法过程总是枯燥的,但为了更好的掌握Gradle,那就必须经过该过程。当然从这一篇将会从零基础开始,开展对Gradle的讲解。1.掌握Gradle基础1.1环境配置去官网下载gradle或者从本地用户文件夹下的.gradle/wrapper/dists找到本地缓存的gradle开发工具包(注意带bin文件夹的这个grade-x.x)系统属性配置:添加GRADLE_HOME:C:\Users\sheji.gradle\wrapper\

    2022年6月28日
    33
  • 说明电磁型继电器的工作原理_永磁继电器工作原理

    说明电磁型继电器的工作原理_永磁继电器工作原理原文地址点击这里:电磁继电器(electromagneticrelay)是一种电子控制器件,它具有控制系统(输入回路)和被控制系统(输出回路),通常应用于自动控制电路中,它是用较小的电流、较低的电

    2022年8月1日
    8
  • unity3D入门_福彩3D深度资料

    unity3D入门_福彩3D深度资料UnityShader中级(Unity2019unity教程初级中级高级扫码时备注或说明中留下邮箱付款后如未回复请加微信630105904联系本博主

    2022年9月19日
    2

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号