棋盘游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 852 Accepted Submission(s): 492
Problem Description
小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限制了只有某些格子才可以放,小希还是很轻松的解决了这个问题(见下图)注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题,在保证尽量多的“车”的前提下,棋盘里有些格子是可以避开的,也就是说,不在这些格子上放车,也可以保证尽量多的“车”被放下。但是某些格子若不放子,就无法保证放尽量多的“车”,这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点,你能解决这个问题么?
Input
输入包含多组数据,
第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M),表示了棋盘的高、宽,以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息:每行两个数X和Y,表示了这个格子在棋盘中的位置。
Output
对输入的每组数据,按照如下格式输出:
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
Sample Output
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
这题主要难点是寻找关键点。不过其实也不算难,先求出最大匹配sum,然后分别将每一个点(x,y)分别去掉,与sum比较,如果比sum小则证明这个点是关键点,以此类推。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int N = 105;
bool map[N][N], flag[N];
int pre[N], c[N*N][2];
int n, m, k;
int find(int cur) //匈牙利算法(二分匹配)
{
int i;
for(i = 1; i <= m; i++)
{
if(map[cur][i] && !flag[i])
{
flag[i] = true;
if(pre[i] == -1 || find(pre[i]))
{
pre[i] = cur;
return 1;
}
}
}
return 0;
}
int run()
{
int i, sum = 0;
memset(pre, -1, sizeof(pre));
for(i = 1; i <= n; i++)
{
memset(flag, false, sizeof(flag));
sum += find(i);
}
return sum;
}
int main()
{
int i, x, y, sum, ans, num, zz = 1;
while(scanf("%d %d %d", &n, &m, &k) != EOF)
{
memset(map, false, sizeof(map));
memset(c, 0, sizeof(c));
for(i = 1; i <= k; i++)
{
scanf("%d %d", &x, &y);
map[x][y] = true; //建图
c[i][0] = x; //行
c[i][1] = y; //列
}
sum = run();
ans = 0;
for(i = 1; i <= k; i++) //分别枚举每条边(x,y)
{
map[ c[i][0] ][ c[i][1] ] = false;
num = run();
if(num < sum) ans++; //比sum少,证明那条边关键点(x,y)
map[ c[i][0] ][ c[i][1] ] = true;
}
printf("Board %d have %d important blanks for %d chessmen.\n", zz++, ans, sum);
}
return 0;
}
- 大小: 2.7 KB
分享到:
相关推荐
二分图的完美匹配是指在一个图中,每个顶点恰好被一条边连接,使得图中的所有顶点都被连接且没有多余未使用的边。在实际应用中,二分图的完美匹配常常出现在分配问题、调度问题等领域。KM算法,即Kuhn-Munkres算法,...
5. **棋盘游戏 (HDU 1281)** - **知识点**:行列匹配问题。 - **解题思路**:构建行列二分图,对于每个行顶点连接该行上的所有列顶点,然后使用最大匹配算法求解。 6. **50 years, 50 colors (HDU 1498)** - *...
通过研究这些代码,你可以学到以下关键知识点: 1. **基础算法**:如排序(冒泡、选择、插入、快速、归并等)、搜索(线性、二分、深度优先、广度优先等)。 2. **高级算法**:包括动态规划(状态转移、记忆化搜索...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
搜索题是 ACM HDU 题目分类中的一大类,例如,1010 搜索题,剪枝很关键;1016 经典的搜索;1026 搜索;1043 经典搜索题,八数码问题;1044 稍微有点麻烦的搜索题;1045 搜索题,可用匹配做 等等。 贪心算法 贪心...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
根据给定的信息,我们可以总结出以下关于二分图检测的相关知识点: ### 一、二分图定义 二分图(Bipartite Graph)是一种特殊的图,在数学领域中,一个图G=(V,E)被称为二分图,如果其顶点集V能被划分成两个互不...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
hdu1001解题报告
在这个章节中,你可能会学到以下几个关键知识点: 1. **深度优先搜索(DFS, Depth-First Search)**:DFS是一种遍历或搜索树(或图)的算法,它沿着树的深度方向进行探索,直到达到叶子节点或者回溯到一个未被访问...
hdu 1574 passed sorce
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
HDU ACM培训资料是一系列专为参与ACM(国际大学生程序设计竞赛)的学员准备的教育资源,涵盖了算法和编程竞赛的核心知识。这份压缩包包含了11个不同主题的课时,旨在帮助学员全面掌握ACM竞赛所需的技能。下面将详细...
ACM HDU题目的解决方案通常会涉及以下知识点: 1. **基础算法**:包括排序(快速排序、归并排序等)、搜索(二分查找、深度优先搜索等)、图论(最短路径、最小生成树等)。 2. **动态规划**:解决许多具有重叠子...
以下是HDU图论题目分类中的部分知识点: 1. 图的基本概念:图的定义、图的表示、图的遍历、图的搜索等。 * 题目1010:Tempter of the Bone,涉及到递归搜索的概念。 * 题目1016:Prime Ring Problem,涉及到递归...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...