poj 1469 COURSES (다이어그램 템플릿 적용 [* 템플릿])

COURSES
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 18454
 
Accepted: 7275
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학생.다음 p행은 각 행이 i과목을 대표하는 줄마다 이 과목의 학생 수를 입력한 다음에 한 번에 이 학생들의 번호를 입력한다.헝가리 알고리즘을 통해 매 과목에 적어도 한 명의 학생이 있다는 것을 보장할 수 있느냐고 물었다.알고리즘 요점: 최대 일치수 >= 과정수 p?
헝가리 알고리즘 코드:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>



using namespace std;



vector<int>g[310];

int link[310], vis[310];

int p, n;



bool match(int x)

{

	for(int i=0; i<g[x].size(); i++ )

	{

		if(!vis[g[x][i]] )

		{

			vis[g[x][i]] = true;

			if(link[g[x][i]]==-1 || match(link[g[x][i]]) )

			{

				link[g[x][i]] = x;

				return true;

			}

		}

	}

	return false;

}





int hungary()

{

	int tot=0;

	memset(link, 255, sizeof(link));

	for(int i=1; i<=n; i++)

	{

		memset(vis, 0, sizeof(vis));

		if(match(i) )

		{

			tot++;

		}

	}

    return tot;

}

int main()

{

	int t;

	int i, j, k;



	scanf("%d", &t);

	while(t--)

	{

		scanf("%d %d", &p, &n);

		int dd, u;

		for(i=1; i<=n; i++)

            g[i].clear();

		for(i=1; i<=p; i++)

		{

			scanf("%d", &dd);

			while(dd--)

			{

				scanf("%d", &u);

				g[u].push_back(i);

			}

		}

		int ans = hungary();

        if(ans >= p)

            printf("YES
");

        else

            printf("NO
");

	}

	return 0;

}

Hopcroft-Karp 알고리즘:
Hopcroft-Karp 알고리즘은 일반적인 헝가리 알고리즘보다 빠르기 때문에 양쪽 집합점이 비교적 많을 때 매칭을 신속하게 완성하기 위해 이 알고리즘을 고려할 수 있다. 템플릿이 있어도 코드가 비교적 길고 번거로우며 잘못 쓰기 쉽다.
두드릴 때 특히 주의하세요!
H-K 알고리즘 코드:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <iostream>

#include <string>

#include <vector>

#include <queue>

#include <algorithm>



using namespace std;

int p, n;

vector<int>g[310];

int n1, n2;

int mx[310], my[310];

queue<int>que;



int dx[310], dy[310];

bool vis[310];





bool find(int u)

{

	for(int i=0; i<g[u].size(); i++)

	{

		if(!vis[g[u][i]] && dy[g[u][i]] == dx[u]+1 )

		{

			vis[g[u][i]] = true;

			if(!my[g[u][i]] || find(my[g[u][i]]) )

			{

				mx[u] = g[u][i];

				my[g[u][i]] = u;

				return true;

			}

		}

	}

	return false;

}



int matching()

{

	memset(mx, 0, sizeof(mx));

	memset(my, 0, sizeof(my));

	int ans=0;



	while(true)

	{

		bool flag=false;

		while(!que.empty())

			que.pop();

		memset(dx, 0, sizeof(dx));

		memset(dy, 0, sizeof(dy));

		for(int i=1; i<=n1; i++)

			if(!mx[i] )

				que.push(i);

		while(!que.empty() )

		{

			int u=que.front();

			que.pop();

			for(int i=0; i<g[u].size(); i++ )

			{

				if(!dy[g[u][i]] )

				{

					dy[g[u][i]] = dx[u]+1;

					if(my[g[u][i]])

					{

						dx[my[g[u][i]]] = dy[g[u][i]] + 1;

						que.push(my[g[u][i]] );

					}

					else

						flag=true;

				}

			}

		}

		if(!flag) break;

		memset(vis, false, sizeof(vis));

		for(int i=1; i<=n1; i++)

		{

			if(!mx[i] && find(i) )

				ans++;

		}

	}

	return ans;

}



int main()

{

	int t;

	scanf("%d", &t);

	int dd, u;

	while(t--)

	{

		scanf("%d %d", &p, &n);

		for(int i=1; i<=n; i++)

            g[i].clear();

		for(int i=1; i<=p; i++)

		{

			scanf("%d", &dd);

			while(dd--)

			{

				scanf("%d", &u);

				g[u].push_back(i);

			}

		}

		n1=n; n2=p;

		int ans = matching();

		if(ans >= p )

		  printf("YES
");

        else

        printf("NO
");



	}

	return 0;

}