POJ训练计划3041_Asteroids(二分图/最小点覆盖=最大匹配)

2024-09-04 08:32

本文主要是介绍POJ训练计划3041_Asteroids(二分图/最小点覆盖=最大匹配),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

解题报告

http://blog.csdn.net/juncoder/article/details/38135053

题目传送门

题意:

给出NxN的矩阵,有M个点是障碍

每次只能删除一行或者一列,最少删除多少次才能清除障碍

思路:

把行和列看作两个集合结点,把障碍看作集合结点的连线,这样就转化成求用最少的点来消灭边,也就是最小点覆盖。

在二分图中:(n个结点,且没有孤立的点)

最小点覆盖=最大匹配

最大点独立=结点数-最大匹配

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 510
using namespace std;
int mmap[N+N][N+N],n,k,vis[N+N],pre[N+N];
int dfs(int x)
{int i;for(i=n+1; i<=n+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,x,y;while(cin>>n>>k) {memset(mmap,0,sizeof(mmap));memset(pre,-1,sizeof(pre));for(i=0; i<k; i++) {cin>>x>>y;mmap[x][n+y]=1;}int ans=0;for(i=1; i<=n; i++) {memset(vis,0,sizeof(vis));ans+=dfs(i);}cout<<ans<<endl;}
}

Asteroids
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14694 Accepted: 8016

Description

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

2

Hint

INPUT DETAILS: 
The following diagram represents the data, where "X" is an asteroid and "." is empty space: 
X.X 
.X. 
.X.
 

OUTPUT DETAILS: 
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

Source

USACO 2005 November Gold



这篇关于POJ训练计划3041_Asteroids(二分图/最小点覆盖=最大匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135509

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Linux中的计划任务(crontab)使用方式

《Linux中的计划任务(crontab)使用方式》:本文主要介绍Linux中的计划任务(crontab)使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、前言1、linux的起源与发展2、什么是计划任务(crontab)二、crontab基础1、cro

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在