BOJ 3139 Antenna Placement //二分图稍稍变形

亦凉 2022-08-10 14:45 82阅读 0赞

# Antenna Placement #

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: [3020][]  
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!

The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.  
![3020_1.jpg][]  
Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?

## Input ##

On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1 <= h <= 40 and 0 < w <= 10. Thereafter is a matrix presented, describing the points of interest in Sweden in the form of h lines, each containing w characters from the set \['\*','o'\]. A '\*'-character symbolises a point of interest, whereas a 'o'-character represents open space.

## Output ##

For each scenario, output the minimum number of antennas necessary to cover all '\*'-entries in the scenario's matrix, on a row of its own.

## Sample Input ##

2
    7 9
    ooo**oooo
    **oo*ooo*
    o*oo**o**
    ooooooooo
    *******oo
    o*o*oo*oo
    *******oo
    10 1
    *
    *
    *
    o
    *
    *
    *
    *
    *
    *

## Sample Output ##

17
    5

## Source ##

[Svenskt M?sterskap i Programmering/Norgesmesterskapet 2001][Svenskt M_sterskap i Programmering_Norgesmesterskapet 2001]

#include <stdio.h>
    #include <string.h>
    
    #define p 1000
    
    bool tu[p][p];
    bool visit[p];
    int r[p], x, y;
    char ch[p][p];
    int ch1[p][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;
    }
    void find(int x1, int y1)
    {
    	int a[5][5] = {
        {-1, 0},{1, 0},{0, -1},{0, 1}};
    	int i;
    
    	for(i=0; i<4; i++)
    	{
    		if((x1+a[i][0]>=0 && x1+a[i][0]<=x) && (y1+a[i][1]>=0 && y1+a[i][1]<=y))
    		{
    			if(ch1[x1+a[i][0]][y1+a[i][1]] != 0)
    				tu[ch1[x1][y1]][ch1[x1+a[i][0]][y1+a[i][1]]] = true;
    		}
    	}
    }
    
    int main()
    {
    	int t;
    	int i, j, k; 
    	int ans;
    
    	scanf("%d", &t);
    	while(t--)
    	{
    		memset(tu, false, sizeof(tu));
    		
    		scanf("%d%d", &x, &y);
    		for(i=0; i<x; i++)
    			scanf("%s", ch[i]);
    
    		k = 0;
    		memset(ch1, 0, sizeof(ch1));
    		for(i=0; i<x; i++)
    		{
    			for(j=0; j<y; j++)
    			{
    				if(ch[i][j]=='*')
    				{
    					k++;
    					ch1[i][j] = k;
    				}
    			}
    		}
    		for(i=1; i<=k; i++)
    			r[i] = -1;
    		for(i=0; i<x; i++)
    		{
    			for(j=0; j<y; j++)
    			{
    				if(ch1[i][j]!=0)
    					find(i, j);
    			}
    		}
    		ans = 0;
    		for(i=1; i<=k; i++)
    		{
    			memset(visit, false, sizeof(visit));
    			if( dfs(i, k) )
    				ans++;
    		}
    		printf("%d\n", k - ans/2);
    	}	
    	return 0;
    }

[3020]: http://acm.pku.edu.cn/JudgeOnline/problem?id=3020
[Prev]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3138
[Submit]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3139#
[Status]: http://www.bnuoj.com/bnuoj/status.php?showpid=3139
[Statistics]: http://www.bnuoj.com/bnuoj/problem_stat.php?pid=3139
[Discuss]: http://www.bnuoj.com/bnuoj/discuss.php?pid=3139
[Next]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3140
[3020_1.jpg]: http://www.bnuoj.com/bnuoj/images/3020_1.jpg
[Svenskt M_sterskap i Programmering_Norgesmesterskapet 2001]: http://www.bnuoj.com/bnuoj/problem.php?search=Svenskt+M%3Fsterskap+i+Programmering%2FNorgesmesterskapet+2001