hdu 1281(最小点覆盖数)
2024-09-04 14:56:17
棋盘游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4097 Accepted Submission(s): 2400
Problem Description
小
希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是
Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。
所以现在
Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量
多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解
决这个问题么?
希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是
Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。
所以现在
Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量
多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解
决这个问题么?
Input
输入包含多组数据,
第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M),表示了棋盘的高、宽,以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息:每行两个数X和Y,表示了这个格子在棋盘中的位置。
第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M),表示了棋盘的高、宽,以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息:每行两个数X和Y,表示了这个格子在棋盘中的位置。
Output
对输入的每组数据,按照如下格式输出:
Board T have C important blanks for L chessmen.
Board T have C important blanks for L chessmen.
Sample Input
3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
Sample Output
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
题意:在图里面删掉哪些点,对减少图的最小点覆盖集??求出点的个数。
题解:没什么好方法,只能一个个点去枚举了。4层循环46MS,数据水炸。
#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = ;
int n,m,k;
int mp[N][N],linker[N];
bool vis[N];
bool dfs(int u){
for(int i=;i<=m;i++){
if(!vis[i]&&mp[u][i]){
vis[i] = true;
if(linker[i]==-||dfs(linker[i])){
linker[i] = u;
return true;
}
}
}
return false;
}
int main()
{
int t = ;
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
int a,b;
memset(mp,,sizeof(mp));
while(k--){
scanf("%d%d",&a,&b);
mp[a][b] = ;
}
int res = ;
memset(linker,-,sizeof(linker));
for(int i=;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) res++;
}
int cnt = ;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]==) continue;
int temp = ;
memset(linker,-,sizeof(linker));
mp[i][j] = ;
for(int k=;k<=n;k++){
memset(vis,false,sizeof(vis));
if(dfs(k)) temp++;
}
if(temp<res) cnt++;
mp[i][j] = ;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n",t++,cnt,res);
}
return ;
}
最新文章
- JAVA可阻塞队列-ArrayBlockingQueue
- linux 下C语言学习路线
- error===>;ld: 2 duplicate symbols for architecture x86_64
- c#读取文本文档实践4-读入到list泛型集合计算后写入新文档
- GTD一些问题
- C语言字符串处理
- 目前国内外主流的linux发行版本
- expdp时遇到ORA-31693&;amp;ORA-02354&;amp;ORA-01466
- Linux-7.2+LNMP+zabbix-3.2.1
- JavaScript写一个表格排序类
- AspNet Core Api Restful 实现微服务之旅 (一)
- New UWP Community Toolkit - Staggered panel
- SwiftyiRate中文说明
- saiku中文维度,补充说明
- spring-boot-oracle spring-batch
- java的方法重写 ,多态和关键字 instanceof和final
- [SQL]批量修改存储过程视图
- Linux(lamp安装)
- window 编译lua 5.3
- python实时得到鼠标的位置
热门文章
- linux网络编程中需要注意的信号SIGPIPE
- Aspose.words 替换字符 操作
- 大数据Hadoop-1
- 【bzoj4052】[Cerc2013]Magical GCD 暴力
- 2017 Multi-University Training Contest - Team 3 Kanade&#39;s trio(字典树+组合数学)
- Codeforces Round #268 (Div. 1) 468D Tree(杜教题+树的重心+线段树+set)
- SPOJ Repeats(后缀数组+RMQ-ST)
- [Leetcode] Copy list with random pointer 对带有任意指针的链表深度拷贝
- LowercaseRoutesMVC ASP.NET MVC routes to lowercase URLs
- NOIP2016愤怒的小鸟 [状压dp]