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)


相关推荐

  • sublime text2 安装及使用教程

    sublime text2 安装及使用教程1.下载安装包地址:https://www.sublimetext.com/22.安装,一直点下一步就好,将下列选项打钩,这样文件右键就可以直接用sublimetext2打开3.新建一个html

  • 基于FPGA的SDRAM控制器设计(4)[通俗易懂]

    基于FPGA完整SDRAM控制器SDRAM控制器接口简述自动读写模块的框图SDRAM控制器完整代码SDRAM控制器的测试代码仿真结果SDRAM控制器接口简述完整的SDRAM控制器的模块框图如下:前面的三篇文章,我们已经简述了基本的SDRAM的基本操作。这里总结一下SDRAM的几个模块,SDRAM的上电初始化,自刷新、读写模块、顶层仲裁控制。了解了上面的操作,我们已经可以完成SDRAM控制器…

  • BS架构和CS架构的优缺点

    BS架构和CS架构的优缺点1、CS、BS架构定义  CS(Client/Server):客户端—-服务器结构。C/S结构在技术上很成熟,它的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。因为客户端要负责绝大多数的业务逻辑和UI展示,又称为胖客户端。它充分利用两端硬件,将任务分配到Client和Server两端,降低了系统的通讯开销。C/S结构的软件需要针对不同的操作系

  • opencv使用教程_opencv使用教程

    opencv使用教程_opencv使用教程OpenCV(OpenSourceComputerVisionLibrary)是一个开源的计算机视觉库,它提供了很多函数,这些函数非常高效地实现了计算机视觉算法(最基本的滤波到高级的物体检测皆有涵盖)。OpenCV使用C/C++开发,同时也提供了Python、Java、MATLAB等其他语言的接口。OpenCV是跨平台的,可以在Windows、Linux、MacOS、Android、iOS等操作系统上运行。OpenCV的应用领域非常广泛,包括图像拼接、图像降噪、产品质检、..

  • vs2013注册_vs2008是什么软件

    vs2013注册_vs2008是什么软件
    VS2008注册方法:
      VS2008注册方法非常简单,在开始>设置>控制面版>添加或删除程序>卸载vs.net2008(名字不太记得了)>出现卸载界面>点击Next>输入上面CD-key->出现成功画面即可完美将试用版升级成为正式版。
    VS2008正式版序列号CDKEY:PYHYP-WXB3B-B2CCM-V9DX9-VDY8T

  • C语言根据经纬度计算距离[通俗易懂]

    C语言根据经纬度计算距离[通俗易懂]#include#defineEARTH_RADIUS6378.137//地球半径#definePI3.14159265358979323846//Ô²ÖÜÂÊ//½Ç¶Èת»¯Îª»¡¶Èstaticdoublerad(doubled){  returnd*PI/180.0;}//µ±Äϱ±

发表回复

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

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