BOJ 3160 Asteroids //二分图水题

古城微笑少年丶 2022-08-10 14:45 124阅读 0赞

# Asteroids #

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: [3041][]  
64-bit integer IO format: %lld 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!

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.  
  
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

## Input ##

\* Line 1: Two integers N and K, separated by a single space.  
\* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

## Output ##

\* Line 1: The integer representing the minimum number of times Bessie must shoot.

## Sample Input ##

3 4
    1 1
    1 3
    2 2
    3 2

## Sample Output ##

## Source ##

[USACO 2005 November Gold][]

#include <stdio.h>
    #include <string.h>
    
    #define p 505
    
    bool tu[p][p];
    bool visit[p];
    int r[p];
    
    bool dfs(int a, int n)
    {
    	int i;
    	for(i=1; 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, k, x, y;
    	int ans;
    	
    	while(scanf("%d%d", &n, &k)!=-1)
    	{
    		ans = 0;
    		memset(tu, false, sizeof(tu));
    		for(i=1; i<=n; i++)
    		{
    			r[i] = -1;
    		}		
    		for(i=0; i<k; i++)
    		{
    			scanf("%d%d", &x, &y);
    			tu[x][y] = true;			
    		}		
    		
    		for(i=1; i<=n; i++)
    		{
    			memset(visit, false, sizeof(visit));
    			if( dfs(i, n) )
    				ans++;
    		}
    		printf("%d\n", ans);
    	}	
    	
    	return 0;
    }

[3041]: http://acm.pku.edu.cn/JudgeOnline/problem?id=3041
[Prev]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3159
[Submit]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3160#
[Status]: http://www.bnuoj.com/bnuoj/status.php?showpid=3160
[Statistics]: http://www.bnuoj.com/bnuoj/problem_stat.php?pid=3160
[Discuss]: http://www.bnuoj.com/bnuoj/discuss.php?pid=3160
[Next]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3161
[USACO 2005 November Gold]: http://www.bnuoj.com/bnuoj/problem.php?search=USACO+2005+November+Gold