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

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

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 随机数算法 java_最全的java随机数生成算法[通俗易懂]

    随机数算法 java_最全的java随机数生成算法[通俗易懂]最全的java随机数生成算法java随机数生成算法是怎么样的?下面yjbys小编为大家分享最新最全的java随机数生成算法,希望对大家学习有所帮助!一个最全的随机数的生成算法,最代码的找回密码的随机数就是用的这个方法:1Stringpassword=RandomUtil.generateString(10);源码如下:001packagecom.javaniu.core.util;00…

  • 用perl获取可用的代理服务器地址

    用perl获取可用的代理服务器地址

  • 万洲金业平台上炒黄金亏损了怎么办?「建议收藏」

    万洲金业平台上炒黄金亏损了怎么办?「建议收藏」  由于受国际行情变化影响,黄金市场很难长时间维持单边走势,因此金价起伏波动不断才是正确的打开方式。尽管黄金价格不断变化为人们营造了良好的盈利空间,但对于大多数人来说,尽管亏损是难以避免的,但真当风险来临,还是难以接受。所以今天就详细介绍一下当人们在万洲金业平台上发生了炒金亏损之后应该怎么办。万洲金业是一家专业的黄金交易平台,为人们提供了极为周到的黄金投资服务,也借助良好的市场表现成为了不少人的炒金选择。即便如此也不能代表平台客户不会发生黄金投资亏损。  在万洲金业平台上炒黄金,一旦发生了交易亏损,

  • phpstorm 2021激活码_在线激活

    (phpstorm 2021激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 51单片机流水灯的三种实现方法「建议收藏」

    51单片机流水灯的三种实现方法「建议收藏」首先,介绍下原理。下图为主控芯片和流水灯模块的原理图。流水灯模块接在单片机的P1口,由原理图可以知道,在P1口给一个低电平即可点亮LED灯。相反,如果要LED灯熄灭,就要把P1口的电平变为高电平即可。要实现流水灯功能,我们只要将LED1~LED8依次点亮、熄灭,依始类推,8只LED变会一亮一暗的做流水灯了。              实现8个LED流水灯程序用中

  • latex中希腊字母_LaTeX怎么念

    latex中希腊字母_LaTeX怎么念日常写论文,ppt作汇报等,经常需要编写公式,为方便查阅希腊字母对应latex表示,特写此表格,以便大家查阅。小写 Latex表示 大写 Latex表示 \alpha A A \beta B B \gamma \Gamma \delta \Delta \epsilon …

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

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