BOJ 5291 Girls and Boys //二分图水题

ゝ一世哀愁。 2022-08-10 14:45 164阅读 0赞

# Girls and Boys #

Time Limit: 10000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: [1068][]  
64-bit integer IO format: %I64d Java class name: Main

[Prev][] [Submit][] [Status][] [Statistics][] [Discuss][] [Next][]

Font Size:\+\-

Type:

None

Graph Theory

2-SAT

Articulation/Bridge/Biconnected Component

Cycles/Topological Sorting/Strongly Connected Component

Shortest Path

Bellman Ford

Dijkstra/Floyd Warshall

Euler Trail/Circuit

Heavy-Light Decomposition

Minimum Spanning Tree

Stable Marriage Problem

Trees

Directed Minimum Spanning Tree

Flow/Matching

Graph Matching

Bipartite Matching

Hopcroft–Karp Bipartite Matching

Weighted Bipartite Matching/Hungarian Algorithm

Flow

Max Flow/Min Cut

Min Cost Max Flow

DFS-like

Backtracking with Pruning/Branch and Bound

Basic Recursion

IDA\* Search

Parsing/Grammar

Breadth First Search/Depth First Search

Advanced Search Techniques

Binary Search/Bisection

Ternary Search

Geometry

Basic Geometry

Computational Geometry

Convex Hull

Pick's Theorem

Game Theory

Green Hackenbush/Colon Principle/Fusion Principle

Nim

Sprague-Grundy Number

Matrix

Gaussian Elimination

Matrix Exponentiation

Data Structures

Basic Data Structures

Binary Indexed Tree

Binary Search Tree

Hashing

Orthogonal Range Search

Range Minimum Query/Lowest Common Ancestor

Segment Tree/Interval Tree

Trie Tree

Sorting

Disjoint Set

String

Aho Corasick

Knuth-Morris-Pratt

Suffix Array/Suffix Tree

Math

Basic Math

Big Integer Arithmetic

Number Theory

Chinese Remainder Theorem

Extended Euclid

Inclusion/Exclusion

Modular Arithmetic

Combinatorics

Group Theory/Burnside's lemma

Counting

Probability/Expected Value

Others

Tricky

Hardest

Unusual

Brute Force

Implementation

Constructive Algorithms

Two Pointer

Bitmask

Beginner

Discrete Logarithm/Shank's Baby-step Giant-step Algorithm

Greedy

Divide and Conquer

Dynamic Programming

Tag it!

the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.  
  
The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:  
  
the number of students  
the description of each student, in the following format  
student\_identifier:(number\_of\_romantic\_relations) student\_identifier1 student\_identifier2 student\_identifier3 ...  
or  
student\_identifier:(0)  
  
The student\_identifier is an integer number between 0 and n-1, for n subjects.  
For each given data set, the program should write to standard output a line containing the result.

## Sample Input ##

7
    0: (3) 4 5 6
    1: (2) 4 6
    2: (0)
    3: (0)
    4: (2) 0 1
    5: (1) 0
    6: (2) 0 1
    3
    0: (2) 1 2
    1: (1) 0
    2: (1) 0

## Sample Output ##

5
    2

## Source ##

[Southeastern Europe 2000][]

#include <stdio.h>
    #include <string.h>
    
    #define p 5000
    
    bool tu[p][p];
    bool visit[p];
    int r[p];
    
    bool dfs(int a, int n)
    {
    	int i;
    	for(i=0; i<n; i++)
    	{
    		if(tu[a][i] && !visit[i])
    		{
    			visit[i] = true;
    			if(r[i]==-1 || dfs(r[i], n))
    			{
    				r[i] = a;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int main()
    {
    	int n;
    	int i, a, k, v;
    	int ans;
    
    	while(scanf("%d", &n)!=-1)
    	{
    		ans = 0;
    		memset(tu, false, sizeof(tu));
    		for(i=0; i<n; i++)
    		{
    			r[i] = -1;
    		}
    
    		for(i=0; i<n; i++)
    		{
    			scanf("%d: ", &a);
    			scanf("(%d)", &k);
    
    			while(k--)
    			{
    				scanf("%d", &v);
    				tu[a][v] = true;
    			}
    		}
    
    		
    		for(i=0; i<n; i++)
    		{
    			memset(visit, false, sizeof(visit));
    			if( dfs(i, n) )
    				ans++;
    		}
    		printf("%d\n", n-ans/2);
    	}
    
    	return 0;
    }

[1068]: http://acm.hdu.edu.cn/showproblem.php?pid=1068
[Prev]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=5290
[Submit]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=5291#
[Status]: http://www.bnuoj.com/bnuoj/status.php?showpid=5291
[Statistics]: http://www.bnuoj.com/bnuoj/problem_stat.php?pid=5291
[Discuss]: http://www.bnuoj.com/bnuoj/discuss.php?pid=5291
[Next]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=5292
[Southeastern Europe 2000]: http://www.bnuoj.com/bnuoj/problem.php?search=Southeastern+Europe+2000