poj 3041 Asteroids(二分图 *【矩阵实现】【最小点覆盖==最大匹配数】)
2024-10-20 11:24:31
Asteroids
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 16379 | Accepted: 8930 |
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.
* 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.
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).
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#define N 500+20
#define INF 0x3f3f3f3f using namespace std;
int n, m;
int map[N][N];
int link[N];
bool vis[N]; bool match( int u )
{
for(int i=1; i<=n; i++)
{
if(vis[i]==false && map[u][i]==1 )
{
vis[i]=true;
if(link[i]==-1 || match(link[i]) )
{
link[i]=u;
return true;
}
}
}
return false;
} int main()
{
int i, j, k;
int u, v;
scanf("%d %d", &n, &m);
memset(map, 0, sizeof(map)); for(i=0; i<m; i++ ){
scanf("%d %d", &u, &v);
map[u][v] = 1;
}
memset(link, -1, sizeof(link));
int ans=0; for(int i=1; i<=n; i++)
{
memset(vis, false, sizeof(vis));
if(match(i))
ans++; }
printf("%d\n", ans );
return 0;
}
最新文章
- mac-改造你的terminal
- RPM方式安装MySQL5.5.48 (Aliyun CentOS 7.0 &; 卸载MySQL5.7)
- hdu 1175冒牌连连看
- Python isdigit()方法
- 转 How to install XenServer Tools – Linux(forward)
- 2013-07-26 IT 要闻速记快想
- Windows操作系统常用快捷键
- uva 10004 Bicoloring(dfs二分染色,和hdu 4751代码差不多)
- oschina程序开发
- Vue安装依赖npm install时报错问题解决方法
- [SQLite]SQLite URI配置
- 为 docker 中的 nginx 配置 https
- python对 if __name__==&#39;__main__&#39;的理解
- Deep Learning Tutorial - Convolutional Neural Networks(LENET)
- mybatis环境配置与入门例子
- Kafka:ZK+Kafka+Spark Streaming集群环境搭建(二十九):推送avro格式数据到topic,并使用spark structured streaming接收topic解析avro数据
- oracle中实现md5加密
- 在阿里云容器服务上开发基于Docker的Spring Cloud微服务应用
- java 监控工具 jconsole
- [BZOJ 2839]集合计数