程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1469_COURSES(二分圖最大匹配)

POJ1469_COURSES(二分圖最大匹配)

編輯：C++入門知識

POJ1469_COURSES(二分圖最大匹配)

解題報告

題目傳送門

題意：

n個學生p門課程，每個學生學習0或1以上的課程。

問：是否可以組成委員會，滿足

每個學生代表一門不同的課程

一門課程在委員會中有一名代表

思路：

很明顯的二分圖的完備匹配。

#include 
#include 
#include 
#include 
#include 
#include 
#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

Sample Output

YES
NO

Source

Southeastern Europe 2000

上一頁:HDU4850 構造一個長度為n的串，要求任意長度為4的子串不相同
下一頁:poj2155--Matrix（二維樹狀數組）

C++入門知識

UVA - 10591 - Happy Number （STL）

UVA - 10591 - Happy Number

C++ 初始化列表(一)

C++ 初始化列表(一) 何謂初始化列表與其他函數不同

世界上最簡單的無鎖哈希表

無鎖哈希表Lock-Free Hash Table ）可

HDU2050

折線分割平面 Time Limit: 2000/100

CF 196 Div 2 D (樹形dp)

CF 196 Div 2 D (樹形dp)

C++死鎖解決心得

一、概述 C++多線程開發中，容易出現死鎖導致程序掛

閱讀排行榜

C++之Effective STL學習筆記Item7 5_1三角形類 Codeforces Round #265 (Div. 2)D. Restore Cube 暴力 POJ 3349 Snowflake Snow Snowflakes POJ 2488 A Knight&#39;s Journey 遞歸回溯題解 poj 3693 Maximum repetition substring (後綴數組) LeetCode----Generate Parentheses POJ 1384 PigBank 解題報告之 POJ1226 Substrings Sicily 1299 Academy Awards （map + vector容器）第16章模板與泛型編程(4)

熱門圖文

ASP.NET Eval進行數據綁定的方法 poj 2299 急用萬分感謝-C++順序讀取txt的問題 JSON 之 SuperObject(14): 從 XML 中解析多線程中如何避免死鎖再學GDI+[100]: TGPImage(20) - 替換顏色(2) c++-在工具欄的一個動作上來顯示提示信息怎麼沒看到？ new-link這段代碼的含義是什麼？看不懂

欄目導航

C++基礎知識 C++入門知識關於C++